Further analysis of the number of spanning trees in circulant graphs. (English) Zbl 1131.05048

Let \(T(C_n^{s_1,s_2,\dots,s_k})=na_n^2\) denote the number of spanning trees of the graph \(C_n^{s_1,s_2,\dots,s_k}\). The authors investigate the numbers \(a_n\) further and, in particular, give asymptotic results on these quantities.


05C30 Enumeration in graph theory
05C05 Trees
Full Text: DOI


[1] Atajan, T.; Yong, X., The number of spanning trees of three special cycles, ()
[2] Baron, G.; Prodinger, H.; Tichy, R.; Boesch, F.; Wang, J., The number of spanning trees in the square of a cycle, Fibonacci quart., 23.3, 258-264, (1985) · Zbl 0587.05040
[3] Bedrosian, S., The Fibonacci numbers via trigonometric expressions, J. franklin inst., 295, 175-177, (1973) · Zbl 0298.05104
[4] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press London
[5] Boesch, F.; Prodinger, H., Spanning tree formulae and Chebyshev polynomials, Graph combin., 2, 191-200, (1986) · Zbl 0651.05028
[6] F. Boesch, J. 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 of Sciences, New York, 1982, p. 16.
[7] Chen, X.; Lin, Q.; Zhang, F., The number of spanning trees in odd valent circulant graphs, Discrete math., 282, 69-79, (2004) · Zbl 1042.05051
[8] Cvetkovie˘, D.; Doob, M.; Sachs, H., Spectra of graphs: theory and applications, (1995), Johann Ambrosius Barth Heidelberg
[9] Golub, G.H.; Van Loan, C.F., Matrix computations, (1989), The Jonhs Hopkins University Press Baltimore, MD · Zbl 0733.65016
[10] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[11] Kirchhoff, G., Uberdie auflosung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer strome geluhrt wird, Ann. phys. chem., 72, 497-508, (1847)
[12] Kleitman, D.; Golden, B., Counting trees in a certain class of graphs, Amer. math. monthly, 82, 40-44, (1975) · Zbl 0297.05123
[13] Mostowski, A.; Stark, M., Introduction to higher algebra, (1964), PWN-Polish Scientific Publishers Warszawa · Zbl 0108.25102
[14] Yong, X.; Atajan, T.; Acenjian, The numbers of spanning trees of the cubic cycle and the quadruple cycle, Discrete math., 169, 293-298, (1997) · Zbl 0879.05036
[15] Zhang, F.; Yong, X., Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs & graphs, Sci. China, ser. A, 43, 2, 264-271, (1999) · Zbl 0929.05018
[16] Y.P. Zhang, Counting the number of spanning trees in some special graphs, Ph.D. Thesis, Hong Kong University of Science and Technology, 2002.
[17] 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. 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.