摘要:

AbstractWe prove that ifGis a connected graph withpvertices and minimum degree greater than max(p/4 − 1,3) thenG2is pancyclic. The result is best possible of its kin

ISSN:0364-9024    

DOI:10.1002/jgt.3190120402

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

年代:1988

数据来源: WILEY

摘要:

AbstractGiven an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. Thepagenumber t(G)(also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showingt(Km,n) ⩽ ⌈(m+ 2n)/4⌉, which we conjecture optimal. We prove a result suggesting this is optimal form⩾ 2n− 3. For the most difficult casem=n, we consider vertex permutations that areregular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ⌈(7n− 2)/9⌉ pages, which is achievable. The general construction uses fewer pages, but with an irr

ISSN:0364-9024    

DOI:10.1002/jgt.3190120403

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

年代:1988

数据来源: WILEY

摘要:

AbstractFor integerspandssatisfying 2 ⩽s⩽ p − 1, letm(p,s) denote the maximum number of edges in a graphGof orderpsuch that the minimum degree in the hamiltonian path graph ofGequalss. The values ofm(p, s) are determined for 2 ⩽ s ⩽ p/2 and for (2p− 2)/3 ⩽s⩽p− 1, and upper and lower bounds onm(p, s) are obtained f

ISSN:0364-9024    

DOI:10.1002/jgt.3190120404

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

年代:1988

数据来源: WILEY

摘要:

AbstractA CycleCof a graphGis called aDλ‐cycle if every component ofG−V(C) has order less than λ ADλ‐path is defined analogously.Dλ‐cycles andDλ‐paths were introduced by Veldman. Here a cycleCof a graphGis called a Δλ‐cycle if all vertices ofGare at distance less than λ from a vertex ofC. A Δλ‐path is defined analogously. In particular, in a connected graph, a Δλ‐cycle is a Δλ‐Cycle and a Δλ‐Path is a Δ‐path. Furthermore, a Δ1‐cycle is a Hamilton cycle and a Δ1path is a Hamilton path. Necessary conditions and sufficient conditions are derived for graphs to have a Δλ‐cycle or Δλ‐path. The results are analogues of theorems onDλ‐cycles andDλ‐paths. In particular, a result of Chvátal and Erdös on Hamilton cycles and Hamiiton paths is ge

ISSN:0364-9024    

DOI:10.1002/jgt.3190120405

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

年代:1988

数据来源: WILEY

摘要:

AbstractNew upper bounds for the ramsey numbersr(k, l) are obtained. In particular it is shown there is a constant A such that

ISSN:0364-9024    

DOI:10.1002/jgt.3190120406

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

年代:1988

数据来源: WILEY

摘要:

AbstractLetr, t⩾ 2 be integers andca constant, 0

ISSN:0364-9024    

DOI:10.1002/jgt.3190120407

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

年代:1988

数据来源: WILEY

摘要:

AbstractThe distance between a pair of verticesu, vin a graphGis the length of a shortest path joininguandv. The diameter diam(G) ofGis the maximum distance between all pairs of vertices inG. A spanning treeTofGis diameter preserving if diam(T) = diam(G). In this note, we characterize graphs that have diameter‐preserving spanning tree

ISSN:0364-9024    

DOI:10.1002/jgt.3190120408

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

年代:1988

数据来源: WILEY

摘要:

AbstractA graph G is radius‐critical if every proper induced connected subgraph ofGhas radius strictly smaller than the original graph. Our main purpose is to characterize all such graph

ISSN:0364-9024    

DOI:10.1002/jgt.3190120409

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

年代:1988

数据来源: WILEY

摘要:

AbstractA graph is pseudo‐median if for every tripleu, v, wof vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs ofu, v, w, respectively (if the distance sum is odd). We show that a finite pseudo‐median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper‐octahedron. Every self‐map of a pseudo‐median graph that preserves or collapses edges has an invariant regular pseudo‐median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo‐median graph induces a regular pseudo‐

ISSN:0364-9024    

DOI:10.1002/jgt.3190120410

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

年代:1988

数据来源: WILEY

摘要:

AbstractA generalization of the chromatic number of a graph is introduced such that the colors are integers modulon, and the colors on adjacent vertices are required to be as far apart as possible.

ISSN:0364-9024    

DOI:10.1002/jgt.3190120411

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

年代:1988

数据来源: WILEY