Some Results on Spanning Trees

被引：16

作者：

Yao, Bing ^{[1
]}

Zhang, Zhong-fu ^{[1
]}

Wang, Jian-fang ^{[2
]}

机构：

[1] NW Normal Univ, Coll Math & Informat Sci, Lanzhou 730070, Peoples R China

[2] Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China

来源：

ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES | 2010年 / 26卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Spanning tree; leaves; diameter; Steiner tree; independent number; LEAVES;

D O I：

10.1007/s10255-010-0011-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Some structures of spanning trees with many or less leaves in a connected graph are determined. We show (1) a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path, and (2) a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Delta(G) = Delta(T) and the number of leaves of T is not greater than n - D(G) + 1, where D(G) is the diameter of G.

引用

页码：607 / 616

页数：10

共 14 条

[1] SPANNING DIRECTED TREES WITH MANY LEAVES
Alon, Noga
Fomin, Fedor V.
Gutin, Gregory
Krivelevich, Michael
Saurabh, Saket
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (01) : 466 - 476
[2] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[3] Connected domination and spanning trees with many leaves
Caro, Y
West, DB
Yuster, R
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (02) : 202 - 211
[4] CZYGRINOW A, 2001, ELECT J COMBINATORIC, V8
[5] Spanning trees with many leaves
Ding, GL
Johnson, T
Seymour, P
[J]. JOURNAL OF GRAPH THEORY, 2001, 37 (04) : 189 - 197
[6] GALLIAN JA, 2009, ELECT J COMBINATORIC, V16
[7] Karp R.M., 1972, PLENUM PRESS SURV ST, P85, DOI 10.1007/978-1-4684-2001-2_9
[8] SPANNING-TREES WITH MANY LEAVES
KLEITMAN, DJ
WEST, DB
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1991, 4 (01) : 99 - 106
[9] LOWER BOUND FOR CIRCUMFERENCE OF A GRAPH
LINIAL, N
[J]. DISCRETE MATHEMATICS, 1976, 15 (03) : 297 - 300
[10] RAJAGOPALAN S, 1999, SODA 99, P742

← 1 2 →