摘要:

AbstractGraham and Pollak [3] proved thatn−1 is the minimum number of edge‐disjoint complete bipartite subgraphs into which the edges ofKncan be decomposed. Using a linear algebraic technique, Tverberg [2] gives a different proof of that result. We apply his technique to show that for “almost alln,” ⌊ (n+m−3)/(m−1) ⌋ is the minimum number of edge‐disjoint completem‐partite subgraphs in a

ISSN:0364-9024    

DOI:10.1002/jgt.3190150102

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe prove that every connected graphGcontains a treeTof maximum degree at mostkthat either spansGor has order at leastkδ(G) + 1, where δ(G) is the minimum degree ofG.This generalizes and unifies earlier results of Bermond [1] and Win [7]. We also show that the square of a connected graph contains a spanning tree of maximum degree at most thre

ISSN:0364-9024    

DOI:10.1002/jgt.3190150103

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

年代:1991

数据来源: WILEY

摘要:

AbstractHarary stated the conjecture that for any graphGwithnedges and without isolated verticesr(K3,G) ⩽ 2n+ 1. Erdös, Faudree, Rousseau, and Schelp proved thatr(K3,G) ⩽ ⌈8/3n⌉. Here we prove thatr(K3,G) ⩽ ⌊5/2

ISSN:0364-9024    

DOI:10.1002/jgt.3190150104

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

年代:1991

数据来源: WILEY

摘要:

AbstractThis paper considers conditions ensuring that cycle‐isomorphic graphs are isomorphic. Graphs of connectivity ⩾ 2 that have no loops were studied in [2] and [4]. Here we characterize all graphsGof connectivity 1 such that every graph that is cycle‐isomorphic toGis also isomorphi

ISSN:0364-9024    

DOI:10.1002/jgt.3190150105

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetGbe a graph of ordernand defineNC(G)= min{|N(u) ∪N(v)| |uv∉E(G)}. A cycleCofGis called adominating cycleorD‐cycleifV(G) ‐V(C) is an independent set. AD‐pathis defined analogously. The following result is proved: ifGis 2‐connected and contains aD‐cycle, thenGcontains aD‐cycle of length at least min{n, 2NC(G)} unlessGis the Petersen graph. By combining this result with a known sufficient condition for the existence of aD‐cycle, a common generalization of Ore's Theorem and several recent “neighborhood union results” is obtained. An analogous result on longD‐pa

ISSN:0364-9024    

DOI:10.1002/jgt.3190150106

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

年代:1991

数据来源: WILEY

摘要:

AbstractThe residueRof a simple graphGof degree sequenceS:d1⩾d2⩾ …︁ ⩾dnis the number of zeros obtained by the iterative process consisting of deleting the first termd1ofS, subtracting 1 from thed1following ones, and sorting down the new sequence. The depth is the numbern‐Rof steps in this algorithm. We prove here some conjectures given by the computer program GRAFFITI, in

ISSN:0364-9024    

DOI:10.1002/jgt.3190150107

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

年代:1991

数据来源: WILEY

摘要:

AbstractAn interval graphGis homogeneously representable if for every vertexvofGthere exists an interval representation ofGwithvcorresponding to an end interval. We show that the homogeneous representation of interval graphs is rooted in a deeper property of a class of graphs that we characterize by forbidden configurations.

ISSN:0364-9024    

DOI:10.1002/jgt.3190150108

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

年代:1991

数据来源: WILEY

摘要:

AbstractLetQndenote the n‐dimensional hypercube. In this paper we derive upper and lower bounds for the crossing numberv(Qn), i.e., the minimum number of edge‐crossings in any planar drawing ofQn. The upper bound is close to a result conjectured by Eggleton and Guy and the lower bound is a significant improvement over what was previously known. LetN= 2nbe the number of vertices ofQn. We show thatv(Qn)0 is a constant and lg is the logarithm base 2. The best lower bound using standard arguments isv(Qn) = Ω(N(lgN)2). The lower bound is obtained by constructing a large family of homeomorphs of a subcube with the property that no given pair of edges can appear in more than a constant number of the homeom

ISSN:0364-9024    

DOI:10.1002/jgt.3190150109

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

年代:1991

数据来源: WILEY

摘要:

AbstractA vertex setYin a (hyper)graph is calledk‐independent if in the sub(hyper)‐graph induced byYevery vertex is incident to less thankedges. We prove a lower bound for the maximum cardinality of ak‐independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán

ISSN:0364-9024    

DOI:10.1002/jgt.3190150110

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

年代:1991

数据来源: WILEY

ISSN:0364-9024    

DOI:10.1002/jgt.3190150101

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

年代:1991

数据来源: WILEY