×

Chebyshev polynomials and spanning tree formulas for circulant and related graphs. (English) Zbl 1070.05029

Summary: 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 F. T. Boesch and H. Prodinger [Graphs Comb. 2, 191–200 (1986; Zbl 0651.05028)] 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 (iii) \(G=K_{n}\pm C\), where \(K_n\) is the complete graph on \(n\) vertices and \(C\) is a circulant graph.

MSC:

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

Citations:

Zbl 0651.05028
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baron, G.; Prodinger, H.; Tichy, R. F.; Boesch, F. T.; Wang, J. F., The number of spanning trees in the square of a cycle, Fibonacci Quart., 23.3, 258-264 (1985) · Zbl 0587.05040
[2] Bedrosian, S., The Fibonacci numbers via trigonometric expressions, J. Franklin Inst., 295, 175-177 (1973) · Zbl 0298.05104
[3] Bedrosian, S. D., Formulas for the number of trees in a networks, IEEE Trans. Circuit Theory, CT-8, 363-364 (1961)
[4] Bedrosian, S. D., Generating formulas for the number of trees in a graph, J. Franklin Inst., 277, 313-326 (1964) · Zbl 0135.41904
[5] Bedrosian, S. D., Formulas for the number of trees in certain incomplete graphs, J. Franklin Inst., 289, 67-69 (1970) · Zbl 0297.05125
[6] Bedrosian, S. D., Tree counting polynomials for labelled graphs, J. Franklin Inst., 312, 417-430 (1981) · Zbl 0477.05046
[7] Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press London
[8] Boesch, F. T.; Prodinger, H., Spanning tree formulas and Chebyshev polynomials, Graph Combin., 2, 191-200 (1986) · Zbl 0651.05028
[9] F.T. Boesch, J.F. Wang, A conjecture on the number of spanning trees in the square of a cycle, in: Notes from New York Graph Theory Day V, New York Academy Sciences, New York, 1982, pp. 16.; F.T. Boesch, J.F. Wang, A conjecture on the number of spanning trees in the square of a cycle, in: Notes from New York Graph Theory Day V, New York Academy Sciences, New York, 1982, pp. 16.
[10] Chartrand, G.; Lesniak, L., Graphs & Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001
[11] Colbourn, C. J., The Combinatorics of Network Reliability (1987), Oxford University Press: Oxford University Press New York
[12] Cvetkovič, D.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Applications (1995), Johann Ambrosius Barth: Johann Ambrosius Barth Heidelberg · Zbl 0824.05046
[13] Gilbert, B.; Myrvold, W., Maximizing spanning trees in almost complete graphs, Networks, 30, 97-104 (1997) · Zbl 0885.90109
[14] M.J. Golin, Y. Zhang, Further applications of Chebyshev polynomials in the derivation of spanning tree formulas for circulant graphs, in: Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of the International Colloquium on Mathematics and Computer Science, Versailles, France, September 16-19, Birkhäuser-Verlag, Basel, 2002, pp. 541-552.; M.J. Golin, Y. Zhang, Further applications of Chebyshev polynomials in the derivation of spanning tree formulas for circulant graphs, in: Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Proceedings of the International Colloquium on Mathematics and Computer Science, Versailles, France, September 16-19, Birkhäuser-Verlag, Basel, 2002, pp. 541-552. · Zbl 1029.05075
[15] Huang, Z. J.; Li, X. M., A general method for finding the number of spanning trees of some types of composite graphs, Acta Math. Sci., 15, 3, 259-268 (1995), (Chinese) · Zbl 0900.05006
[16] Kel’mans, A. K.; Chelnokov, V. M., A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory (B), 16, 197-214 (1974) · Zbl 0277.05104
[17] 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)
[18] Kleitman, D. J.; Golden, B., Counting trees in a certain class of graphs, Amer. Math. Monthly, 82, 40-44 (1975) · Zbl 0297.05123
[19] Nikolopoulos, S. D.; Rondogiannis, P., On the number of spanning trees of multi-star related graph, Inform. Process. Lett., 65, 183-188 (1998) · Zbl 1339.05191
[20] O’Neil, P. V., The number of spanning trees in a certain network, Notices Amer. Math. Soc., 10, 569 (1963)
[21] O’Neil, P. V., Enumeration of spanning trees in certain graphs, IEEE Trans. Circuit Theory, CT-17, 250 (1970) · Zbl 0229.05121
[22] O’Neil, P. V.; Slepian, P., The number of trees in a network, IEEE Trans. Circuit Theory, CT-13, 271-281 (1966) · Zbl 0171.22501
[23] Weinberg, L., Number of trees in graph, Proc. IRE, 46, 1954-1955 (1958)
[24] Yan, W. M.; Myrvold, W.; Chung, K. L., A formula for the number of spanning trees of a multi-star related graph, Inform. Process. Lett., 68, 295-298 (1998) · Zbl 1339.05192
[25] Yong, X.; Talip; Acenjian, The numbers of spanning trees of the cubic cycle \(C_N^3\) and the quadruple cycle \(C_N^4\), Discrete Math., 169, 293-298 (1997) · Zbl 0879.05036
[26] Yong, X.; Zhang, F. J., A simple proof for the complexity of square cycle \(C_p^2\), J. Xinjiang Univ., 11, 12-16 (1994)
[27] Zhang, Y. P.; Yong, X.; Golin, M. J., The number of spanning trees in circulant graphs, Discrete Math., 223, 337-350 (2000) · Zbl 0969.05036
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.