摘要:

AbstractThe class of self‐complementary symmetric graphs is characterized using the classification of finite simple grou

ISSN:0364-9024    

DOI:10.1002/jgt.3190160102

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

年代:1992

数据来源: WILEY

摘要:

AbstractFor a graphG, letg(G) and σg(G) denote, respectively, the girth ofGand the number of cycles of lengthg(G) inG. In this paper, we first obtain an upper bound for σg(G) and determine the structure of a 2‐connected graphGwhen σg(G) attains the bound. These extremal graphs are then more‐or‐less classified, but one case leads to an unsolved problem. The structural results are finally applied to show that certain families of graphs are chromaticall

ISSN:0364-9024    

DOI:10.1002/jgt.3190160103

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

年代:1992

数据来源: WILEY

摘要:

AbstractA marked graph is obtained from a graph by giving each point either a positive or a negative sign. Beineke and Harary raised the problem of characterzing consistent marked graphs in which the product of the signs of the points is positive for every cycle. In this paper a characterization is given in terms of fundamental cycles of a cycle basis.

ISSN:0364-9024    

DOI:10.1002/jgt.3190160104

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

年代:1992

数据来源: WILEY

摘要:

AbstractWe shall investigate the behavior of the Ramsey functionr(L, Tn), whereLis a fixed graph andTnis a tree onnvertices, whilen← ∞. We prove that in this case the appropriate Ramsey problem can be reduced to a corresponding Turán type extremal problem: if we take a maximumNfor which aKNcan be colored in two colors so that the first color contains noLand the second color contains noTn, then by the results of Erdös, Faudree, Rousseau and Schelp,N= (p‐ 1)n+ 0(n), wherepis the chromatic number ofL. We shall prove that in the corresponding Ramsey‐coloring the edges of the first color from an “almost Turán graph” onp‐ 1 classes. We shall also describe how the finer structure ofLinfluences this Ramsey number and the stability of the Ramsey coloring. The most important new results—compared with some earlier results—are that we can guarantee structural properties of th

ISSN:0364-9024    

DOI:10.1002/jgt.3190160105

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

年代:1992

数据来源: WILEY

摘要:

AbstractWe give a new condition involving degrees sufficient for a digraph to be hamiltonian.

ISSN:0364-9024    

DOI:10.1002/jgt.3190160106

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

年代:1992

数据来源: WILEY

摘要:

AbstractArooted graphis a pair (G, x) whereGis a simple undirected graph andxϵV(G). IfGif rooted atx, then itsrotation number h(G, x)is teh minimum number of edges in a graphF, of the same order asG, such that for allvϵV(F)we can find a copy ofGinFwith the rootxatv. Rotation numbers for complete bipartite graphs were itroduced in [4] by Cockayne and Lorimer. Several cases were evaluated by Bollobás and Cockayne in [2], and in this paper we give a full soluti

ISSN:0364-9024    

DOI:10.1002/jgt.3190160107

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

年代:1992

数据来源: WILEY

摘要:

AbstractFor everyr‐graphGlet π(G) be the minimal real number ϵ such that for every ϵ<0 andnϵn0(λ,G) everyR‐graphHwithnvertices and more than (π + ϵ)(nr) edges contains a copy ofG. The real number λ(G) is defined in the same way, adding the constraint that all independent sets of vertices inHhave size 0(n). Erdös and Sós asked whether there existr‐graphsGwith π(G)<λ(G)<0. Frankl and Rödl proved that there exist infinitely many suchr‐graphs for everyr≦ 3. However, no example of anr‐graph with above property was known. We construct an example of such a 3‐graph w

ISSN:0364-9024    

DOI:10.1002/jgt.3190160108

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

年代:1992

数据来源: WILEY

摘要:

AbstractA Short proof is given of the theorem that every grph that does not haveK4as a subcontraction is properly vertex 3‐colorabl

ISSN:0364-9024    

DOI:10.1002/jgt.3190160109

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

年代:1992

数据来源: WILEY

摘要:

AbstractA graphgof diameter 2 is minimal if the deletion of any edge increases its diameter. Here the following conjecture of Murty and Simon is proved forn

ISSN:0364-9024    

DOI:10.1002/jgt.3190160110

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

年代:1992

数据来源: WILEY

摘要:

AbstractThe Ramsey numberR(3, 8) can be defined as the least numbernsuch that every graph onnvertices contains either a triangle or an independent set of size 8. With the help of a substantial amount of computation, we prove thatR(3, 8)=28.

ISSN:0364-9024    

DOI:10.1002/jgt.3190160111

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

年代:1992

数据来源: WILEY