Chebyshev polynomials and spanning tree formulas for circulant and related graphs

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 [9] 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 (ii) G = K_n ± C where K_n is the complete graph on n vertices and C is a circulant graph.