Spanning tree formulas and chebyshev polynomials

The Kirchhoff Matrix Tree Theorem provides an efficient algorithm for determiningt(G), the number of spanning trees of any graphG, in terms of a determinant. However for many special classes of graphs, one can avoid the evaluation of a determinant, as there are simple, explicit formulas that give the value oft(G). In this work we show that many of these formulas can be simply derived from known properties of Chebyshev polynomials. This is demonstrated for wheels, fans, ladders, Moebius ladders, and squares of cycles. The method is then used to derive a new spanning tree formula for the complete prismR _n (m) =K _m ×C _n . It is shown that $$2^{\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\left( {1 - \frac{1}{{r - 1}} + o\left( 1 \right)} \right)} $$ whereT _n (x) is then ^th order Chebyshev polynomial of the first kind.