摘要:

AbstractThe upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improve

ISSN:0364-9024    

DOI:10.1002/jgt.3190150402

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

年代:1991

数据来源: WILEY

摘要:

AbstractA nonempty setCof vertices is a star‐cutset in a graphGifG–Cis disconnected and some vertex inCis adjacent to all the remaining vertices inC.Vašek Chvátal proposed to call a graphGunbreakable if neitherGnor its complementGhas a star‐cutset. A path with four vertices and three edges will be termed aP4. An edgeuvof a graphGis called a wing, if for some verticesx, y, {u,v,x,y} induces aP4inG. We define recursively the coercion classCuvof a winguvas follows:1uv∈Cuv, and1ifxy∈Cuvandxy, x'y'are wings of a sameP4inG, thenx'y'∈Cuv.The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbre

ISSN:0364-9024    

DOI:10.1002/jgt.3190150403

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetmandnbe nonnegative integers. Denote byP(m,n) the set of all triangle‐free graphsGsuch that for any independentm‐subsetMand anyn‐subsetNofV(G) withM∩N= Ø, there exists a unique vertex ofGthat is adjacent to each vertex inMand nonadjacent to any vertex inN. We prove that ifm⩾ 2 andn⩾ 1, thenP(m,n) = Ø wheneverm⩽n, andP(m,n) = {Km,n+1} wheneverm>n. We also haveP(1,1) = {C5} andP(1,n) = Ø forn⩾ 2. In the degenerate cases, the classP(0,n) is completely determined, whereas the classP(m,0), which is most interesting, being rich in graphs, is pa

ISSN:0364-9024    

DOI:10.1002/jgt.3190150404

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

年代:1991

数据来源: WILEY

摘要:

AbstractA conjecture of Dirac states that every simple graph withnvertices and 3n− 5 edges must contain a subdivision ofK5. We prove that a topologically minimal counterexample is 5‐connected, and that no minor‐minimal counterexample containsK4–e. Consequently, Dirac's conjecture holds for all graphs that can be embedded in a surface with Euler characteristic at le

ISSN:0364-9024    

DOI:10.1002/jgt.3190150405

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetGbe a graph embedded in the Klein bottle with “representativity” at least four. We give a formula for the orientable genus ofG, which also implies a polynomially bounded algorithm. The formula is in terms of the number of times certain closed curves on the Klein bottle intersect the graph. In particular, it shows that a cut‐and‐paste technique for re‐embedding graphs is the best

ISSN:0364-9024    

DOI:10.1002/jgt.3190150406

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

年代:1991

数据来源: WILEY

摘要:

AbstractA necessary and sufficient condition is obtained for a set of 12 vertices in any 3‐connected cubic graph to lie on a common cycl

ISSN:0364-9024    

DOI:10.1002/jgt.3190150407

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

年代:1991

数据来源: WILEY

摘要:

AbstractDirac (1962) showed that the planar graphs with no prism minor are the graphs obtainable by 2‐sums from bonds, cycles, wheels andK5\e's. We give a new characterization of these graphs in terms of an optimization problem defined on the cycle bases of a grap

ISSN:0364-9024    

DOI:10.1002/jgt.3190150408

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetGbe a graph onnvertices andN2(G) denote the minimum size ofN(u) ∪N(v) taken over all pairs of independent verticesu, vofG. We show that ifGis 3‐connected andN2(G) ⩾ ½(n+ 1), thenGhas a Hamilton cycle. We show further that ifGis 2‐connected andN2(G) ⩾ ½(n+ 3), then eitherGhas a Hamilton cycle or elseGbelongs to one of three families of excepti

ISSN:0364-9024    

DOI:10.1002/jgt.3190150409

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

年代:1991

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190150401

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

年代:1991

数据来源: WILEY