Chebyshev polynomials and spanning tree formulas for circulant and related graphs

doi:10.1016/j.disc.2004.10.025

CORC > 兰州理工大学 > 兰州理工大学

	Chebyshev polynomials and spanning tree formulas for circulant and related graphs
	Zhang, Yuanping 1; Yong, Xuerong 3; Golin, Mordecai J.2
	2005-08-06
关键词	Matrix algebra Polynomials Theorem proving Chebyshev polynomials Circulant graphs Matrix tree theorem Spanning trees
卷号	298
期号	1-3
DOI	10.1016/j.disc.2004.10.025
页码	334-364
英文摘要	Kirchhoff 's Matrix Tree Theorem permits the calculation of the number of spanning trees in any given graph G through the evaluation of the determinant of an associated matrix. In the case of some special graphs Boesch and Prodinger [Graph Combin. 2 (1986) 191-200] have shown how to use properties of Chebyshev polynomials to evaluate the associated determinants and derive closed formulas for the number of spanning trees of graphs. In this paper, we extend this idea and describe how to use Chebyshev polynomials to evaluate the number of spanning trees in G when G belongs to one of three different classes of graphs: (i) when G is a circulant graph with fixed jumps (substantially simplifying earlier proofs), (ii) when G is a circulant graph with some non-fixed jumps and when (iii) G=Kn±C, where Kn is the complete graph on n vertices and C is a circulant graph. © 2005 Elsevier B.V. All rights reserved.
会议录	Discrete Mathematics
会议录出版者	Elsevier
语种	英语
ISSN号	0012365X
WOS研究方向	Mathematics
WOS记录号	WOS:000231739000019
内容类型	会议论文
源URL	[http://ir.lut.edu.cn/handle/2XXMBERH/117093]
专题	兰州理工大学
作者单位	1.School of Computer and Communication, Lanzhou University of Technology, Lanzhou, 730050 Gansu, China; 2.Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong 3.DIMACS, CoRE Building, Rutgers University, Piscataway, NJ 08854-8018, United States;
推荐引用方式 GB/T 7714	Zhang, Yuanping,Yong, Xuerong,Golin, Mordecai J.. Chebyshev polynomials and spanning tree formulas for circulant and related graphs[C]. 见:.