Heavy cycles and spanning trees with few leaves in weighted graphs

被引：1

作者：

Li, Binlong ^{[1
]}

Zhang, Shenggui ^{[1
]}

机构：

[1] Northwestern Polytech Univ, Dept Appl Math, Xian 710072, Shaanxi, Peoples R China

来源：

APPLIED MATHEMATICS LETTERS | 2011年 / 24卷 / 06期

关键词：

Weighted graphs; Heavy cycles; Spanning trees;

D O I：

10.1016/j.aml.2010.12.049

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G be a 2-connected weighted graph and k >= 2 an integer. In this note we prove that if the sum of the weighted degrees of every k + 1 pairwise nonadjacent vertices is at least m, then G contains either a cycle of weight at least 2m/(k + 1) or a spanning tree with no more than k leaves. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：908 / 910

页数：3

共 15 条

[1] [Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[2] Bondy J., 1989, Ann Discrete Math, V41, P53, DOI [10.1016/S0167-5060(08)70449-7, DOI 10.1016/S0167-5060(08)70449-7]
[3] Bondy J., 2002, Discuss Math Graph Theory, V22, P7, DOI [10.7151/dmgt.1154, DOI 10.7151/DMGT.1154]
[4] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[5] Heavy cycles in k-connected weighted graphs with large weighted degree sums
Chen, Bing
Zhang, Shenggui
Cheng, T. C. Edwin
[J]. DISCRETE MATHEMATICS, 2008, 308 (20) : 4531 - 4543
[6] Chen B, 2008, ARS COMBINATORIA, V87, P393
[7] Chen B, 2007, LECT NOTES COMPUT SC, V4489, P338
[8] Chen B, 2007, LECT NOTES COMPUT SC, V4381, P21
[9] Enomoto H, 2005, ARS COMBINATORIA, V76, P225
[10] ON A CONJECTURE OF BONDY
FOURNIER, I
FRAISSE, P
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (01) : 17 - 26

← 1 2 →