The number of spanning trees of a graph

被引：15
作者：
Li, Jianxi [1 ]
Shiu, Wai Chee [1 ]
Chang, An [2 ]
机构：
[1] Hong Kong Baptist Univ, Dept Math, Kowloon Tong, Hong Kong, Peoples R China
[2] Fuzhou Univ, Software Coll, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China
来源：
APPLIED MATHEMATICS LETTERS | 2010年 / 23卷 / 03期
基金：
美国国家科学基金会;
关键词：
Spanning trees; Graph; Bound; ALGEBRAIC CONNECTIVITY;
D O I：
10.1016/j.aml.2009.10.006
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we present some sharp upper bounds for the number of spanning trees of a connected graph in terms of its structural parameters such as the number of vertices, the number of edges, maximum vertex degree, minimum vertex degree, connectivity and chromatic number. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码：286 / 290
页数：5
相关论文
共 11 条
[1]  
[Anonymous], 2001, ALGEBRAIC GRAPH THEO, DOI DOI 10.1007/978-1-4613-0163-9
[2]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[3]   MAXIMIZING THE TOTAL NUMBER OF SPANNING-TREES IN A GRAPH - 2 RELATED PROBLEMS IN GRAPH-THEORY AND OPTIMUM DESIGN THEORY [J].
CHENG, CS .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 31 (02) :240-248
[4]   A sharp upper bound for the number of spanning trees of a graph [J].
Das, Kinkar Ch. .
GRAPHS AND COMBINATORICS, 2007, 23 (06) :625-632
[5]   SHARP UPPER BOUNDS FOR THE NUMBER OF SPANNING TREES OF A GRAPH [J].
Feng, Lihua ;
Yu, Guihai ;
Jiang, Zhengtao ;
Ren, Lingzhi .
APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2008, 2 (02) :255-259
[6]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[7]   UPPER BOUND FOR NUMBER OF SPANNING TREES OF A GRAPH [J].
GRIMMETT, GR .
DISCRETE MATHEMATICS, 1976, 16 (04) :323-324
[8]   THE LAPLACIAN SPECTRUM OF A GRAPH .2. [J].
GRONE, R ;
MERRIS, R .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) :221-229
[9]   A bound on the algebraic connectivity of a graph in terms of the number of cutpoints [J].
Kirkland, S .
LINEAR & MULTILINEAR ALGEBRA, 2000, 47 (01) :93-103
[10]  
Li J, 2002, SYMBIOSIS, V32, P1
12