|
1. |
On the decomposition ofKninto completem‐partite graphs |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 1-6
Qingxue Huang,
Preview
|
PDF (194KB)
|
|
摘要:
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
|
2. |
On the largest tree of given maximum degree in a connected graph |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 7-13
Y. Caro,
I. Krasikov,
Y. Roditty,
Preview
|
PDF (258KB)
|
|
摘要:
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
|
3. |
An upper bound on the ramsey numberR(K3,G) depending only on the size of the graphG |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 15-17
A. F. Sidorenko,
Preview
|
PDF (135KB)
|
|
摘要:
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
|
4. |
On the cycle‐isomorphism of graphs |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 19-27
Xingxing Yu,
Preview
|
PDF (336KB)
|
|
摘要:
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
|
5. |
Long dominating cycles and paths in graphs with large neighborhood unions |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 29-38
H. J. Broersma,
H. J. Veldman,
Preview
|
PDF (412KB)
|
|
摘要:
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
|
6. |
On the residue of a graph |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 39-64
O. Favaron,
M. Mahéo,
J.‐F. Saclé,
Preview
|
PDF (914KB)
|
|
摘要:
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
|
7. |
On the homogeneous representation of interval graphs |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 65-80
Stephan Olariu,
Preview
|
PDF (704KB)
|
|
摘要:
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
|
8. |
Bounds for the crossing number of theN‐cube |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 81-97
Tom Madej,
Preview
|
PDF (658KB)
|
|
摘要:
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
|
9. |
Improved lower bounds onk‐independence |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page 99-107
Yair Caro,
Zsolt Tuza,
Preview
|
PDF (418KB)
|
|
摘要:
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
|
10. |
Masthead |
|
Journal of Graph Theory,
Volume 15,
Issue 1,
1991,
Page -
Preview
|
PDF (31KB)
|
|
ISSN:0364-9024
DOI:10.1002/jgt.3190150101
出版商:Wiley Subscription Services, Inc., A Wiley Company
年代:1991
数据来源: WILEY
|
|