Spanning tree formulas and chebyshev polynomials

The Kirchhoff Matrix Tree Theorem provides an efficient algorithm for determining t(G), the number of spanning trees of any graph G, 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 of t(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 prism Rn(m) =Km ×Cn. It is shown that {Mathematical expression} where Tn(x) is the nth order Chebyshev polynomial of the first kind. © 1986 Springer-Verlag.