Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/20885

Chebyshev polynomials and spanning tree formulas for circulant and related graphs

Authors Zhang, YP
Yong, XR
Golin, MJ View this author's profile
Issue Date 2005
Source Discrete mathematics , v. 298, (1-3, Sp. Iss. SI), 2005, AUG 6, p. 334-364
Summary 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 = K-n +/- C, where K-n is the complete graph on n vertices and C is a circulant graph. (c) 2005 Elsevier B.V. All rights reserved.
Subjects
ISSN 0012-365X
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST