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

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.)
Full Text:

### Online Encyclopedia of Integer Sequences:

Array read by antidiagonals: total number of spanning trees R_n(m) of the complete prism K_m X C_n.

### References:

  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  Bellman, R.: Introduction to Matrix Analysis. New York: McGraw Hill 1970 · Zbl 0216.06101  Biggs, N.: Algebraic Graph Theory. London: Cambridge University Press 1974 · Zbl 0284.05101  Boesch, F., Bogdanowicz, Z.: The number of spanning trees in a prism. Stevens Institute Computer Science Report 8405 (1984) · Zbl 0682.05029  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  Feussner, W.: Zur Berechnung der Stromsträrke in netzförmigen Leitern. Ann. Phys.15, 385–394 (1904) · JFM 35.0886.02  Harry, F.: Graph Theory. Reading: Addison-Wesley 1969 · Zbl 0257.16024  Hilton, A.J.W.: Spanning trees and Fibonacci and Lucas numbers. Fibonacci Q.12, 259–262 (1974) · Zbl 0311.10012  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  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)  Kleitman, D.J., Golden, B.: Counting trees in a certain class of graphs. Amer. Math. Mon.82, 40–44 (1975) · Zbl 0297.05123  Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Boston: Allyn and Bacon 1964 · Zbl 0126.02404  Moon, J.W. Counting Labelled Trees. Canadian Mathematical Congress Monograph 1. London: William Clowes & Sons 1970 · Zbl 0214.23204  Sachs, H.: Über selbstkomplementäre Graphen. Publ. Math. Debrecen9, 270–288 (1962) · Zbl 0119.18904  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  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  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  Sedlácěk, J.: On the spanning trees of finite graphs. Cas. Pestovani Mat.94, 217–221 (1969)  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  Snyder, M.: Chebyshev Methods in Numerical Analysis. Englewood Cliffs: Prentice-Hall 1966 · Zbl 0173.44102  Temperley, H.: On the mutual cancellation of cluster integrals in Mayer’s fugacity series. Proc. Phys. Soc. Lond. Ser. A83, 3–16 (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.