Spanning tree formulas and Chebyshev polynomials. (English) Zbl 0651.05028

Boesch, F. T.; Prodinger, H.

Graphs Comb. 2, 191-200 (1986).

Summary: 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 \(R_ n(m)=K_ m\times C_ n\). It is shown that \[ t(R_ n(m))\quad =\quad \frac{n}{m}2^{m- 1}[T_ n(1\quad +\quad \frac{m}{2})_{-1}]^{m-1} \] where \(T_ n(x)\) is the nth order Chebyshev polynomial of the first kind.

MSC:

05C05	Trees
05C30	Enumeration in graph theory
33C45	Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)

Keywords:

number of spanning trees; Chebyshev polynomials; spanning tree formula; complete prism

References:

[1]	Baron, G., Boesch, F., Prodinger, H., Tichy, R., Wang, J.: The number of spanning trees in the square of a cycle. Fibonacci Q. (to appear) · Zbl 0587.05040
[2]	Bellman, R.: Introduction to Matrix Analysis. New York: McGraw Hill 1970 · Zbl 0216.06101
[3]	Biggs, N.: Algebraic Graph Theory. London: Cambridge University Press 1974 · Zbl 0284.05101
[4]	Boesch, F., Bogdanowicz, Z.: The number of spanning trees in a prism. Stevens Institute Computer Science Report 8405 (1984) · Zbl 0682.05029
[5]	Boesch, F.T., Wang, J.F.: A conjecture on the number of spanning trees in the square of a cycle. In: Notes from New York Graph Theory Day V, p. 16. New York: New York Academy Sciences 1982
[6]	Feussner, W.: Zur Berechnung der Stromsträrke in netzförmigen Leitern. Ann. Phys.15, 385–394 (1904) · JFM 35.0886.02
[7]	Harry, F.: Graph Theory. Reading: Addison-Wesley 1969 · Zbl 0257.16024
[8]	Hilton, A.J.W.: Spanning trees and Fibonacci and Lucas numbers. Fibonacci Q.12, 259–262 (1974) · Zbl 0311.10012
[9]	Kel’mans, A.K., Chelnokov, V.M.: A certain polynomial of a graph and graphs with an extremal number of trees. J. Comb. Theory (B)16, 197–214 (1974) · Zbl 0277.05104
[10]	Kirchhoff, G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem.72, 497–508 (1847)
[11]	Kleitman, D.J., Golden, B.: Counting trees in a certain class of graphs. Amer. Math. Mon.82, 40–44 (1975) · Zbl 0297.05123
[12]	Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Boston: Allyn and Bacon 1964 · Zbl 0126.02404
[13]	Moon, J.W. Counting Labelled Trees. Canadian Mathematical Congress Monograph 1. London: William Clowes & Sons 1970 · Zbl 0214.23204
[14]	Sachs, H.: Über selbstkomplementäre Graphen. Publ. Math. Debrecen9, 270–288 (1962) · Zbl 0119.18904
[15]	Schwenk, A., Wilson, R.: On the eigenvalues of a graph. In: Selected Topics in Graph Theory, edided by Beineke, Wilson, pp. 307–336. New York: Academic Press 1978
[16]	Schwenk, A.: Computing the characteristic polynomial of a graph. In: Graphs and Combinatorics, Lecture Notes in Mathematics406, pp. 153–172. Berlin-Heidelberg-New York: Springer-Verlag 1974 · Zbl 0308.05121
[17]	Sedlácěk, J.: Lucas numbers in graph theory. In: Mathematics-Geometry and Graph Theory (in Czechoslovak), pp. 111–115. Prague: Univ. Karlova 1970. See also Sedlácěk, J.: Ungerichtete Graphen und ihre Gerüste. In: Beiträge zur Graphen Theorie, edited by (H. Sachs, H.-J. Vosz, H. Walther, pp. 143–146. Leipzig: Teubner 1968
[18]	Sedlácěk, J.: On the spanning trees of finite graphs. Cas. Pestovani Mat.94, 217–221 (1969)
[19]	Sedlácěk, J.: On the skeletons of a graph or digraph. In: Combinatorial Structures and their Applications, editded by R. Guy, M. Hanani, N. Saver, J. Schonheim, pp. 387–391. New York: Gordon and Breach 1970
[20]	Snyder, M.: Chebyshev Methods in Numerical Analysis. Englewood Cliffs: Prentice-Hall 1966 · Zbl 0173.44102
[21]	Temperley, H.: On the mutual cancellation of cluster integrals in Mayer’s fugacity series. Proc. Phys. Soc. Lond. Ser. A83, 3–16 (1964)