摘要:

AbstractLetGbe ak‐connected graph of ordern. For an independent set c, letd(S)be the number of vertices adjacent to at least one vertex ofSand>let i(S) be the number of vertices adjacent to at least |S| vertices ofS. We prove that if there exists some s, 1 ≤ s ≤ k, such that ΣxiEXd(X\{Xi})>s(n−1) – k[s/2] –i(X)[(s−1)/2] holds for every independetn set X ={x0, x1⃛xs} of s + 1 vertices, thenGis hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervie

ISSN:0364-9024    

DOI:10.1002/jgt.3190160602

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

摘要:

AbstractA maximally edge‐connected digraph is called super‐λ if every minimum edge disconnecting set is trivial, i.e., it consists of the edges adjacent to or from a given vertex. In this paper sufficient conditions for a digraph to be super‐λ are presented in terms of parameters such as diameter and minimum degree. Similar results are also given for bipartite digraphs. As a corollary, some characterizations of super‐λ graphs and bipartite graphs are obtained. © 1929 John Wile

ISSN:0364-9024    

DOI:10.1002/jgt.3190160603

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

摘要:

AbstractThe star‐chromatic number of a graph, a concept introduced by Vince, is natural generalization of the chromatic number of a graph. We point out an alternate definition of the star‐chromatic number, which sheds new light on the relation of the star‐chromatic number and the ordinary chromatic number. This new point of view allows us to answer several problems posed by Vince. We then study the starchromatic number from the perspective of graph homomorphisms and of graph pro

ISSN:0364-9024    

DOI:10.1002/jgt.3190160604

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

摘要:

AbstractWe consider finite undirected loopless graphsGin which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimaln≥ 0 with the following property: IfGis ann‐edge‐connected graph,s1, ⃛,sk,t1, ⃛,tkare vertices ofG, andf1, ⃛,fl,g1, ⃛,gl, are pairwise distinct edges ofG, then for eachi= 1, ⃛,kthere exists a pathPiinG, connectingsiandtiand for eachi= 1, ⃛,lthere exists a cycleCiinGcontainingfiandgisuch thatP1, ⃛,Pk,C1, ⃛,Clare pairwise edge‐disjoint. We give upper an

ISSN:0364-9024    

DOI:10.1002/jgt.3190160605

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

摘要:

AbstractWe investigate the behavior of the functionf=f(n, k, e)defined as the smallest integer with the following property: If in a graph onnvertices, the numbers of edges in any two induced subgraphs onkvertices differ by at moste, then the graph or its complement has at mostfedges. One of the results states that\documentclass{article}\pagestyle{empty}\begin{document}$$ f(n,k,e) =e\;{\rm for}\,n \ge (2\sqrt 2 + \varepsilon)e^{3/2} \,{\rm and}\,{\rm 2e + 2} \le {\rm k} \le n - 4e - 3 $$\end{document}. © 1929 John Wiley&Sons, Inc

ISSN:0364-9024    

DOI:10.1002/jgt.3190160606

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

摘要:

AbstractA homogeneous graph is a graph togerther with a group that acts transitively on vertices as symmertries of the graph. We consider Laplacians of homogeneous graphs and generalizations of Laplacians whose eigenvalues can be associated with various equilibria of forces in molecules (such as vibrational modes of buckyballs). Methods are given for calculating such eigenvalues by combining concepts and techniques in group representation theory, gauge theory and graph theory.

ISSN:0364-9024    

DOI:10.1002/jgt.3190160607

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

摘要:

AbstractRosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced completer‐partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced completer‐partite graph. Rosenfeld's result had been generalized recently to completer‐partite graphs by Yap (1989). The main result of this paper is to prove that the total chromatic number of every completer‐partite graphGof odd order is Δ (G) + 1. This result gives a partial generalization of Bermond's

ISSN:0364-9024    

DOI:10.1002/jgt.3190160608

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190160601

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1992

数据来源: WILEY