×

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.

MSC:

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

References:

[1] Atajan, T.; Yong, X., The number of spanning trees of three special cycles, (Proceedings of Zheng Zhou Conference on Computing. Proceedings of Zheng Zhou Conference on Computing, China (1994))
[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: 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.; 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: Johann Ambrosius Barth Heidelberg · Zbl 0824.05046
[9] Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), The Jonhs Hopkins University Press: The Jonhs Hopkins University Press Baltimore, MD · Zbl 0733.65016
[10] Harary, F., Graph Theory (1969), Addison-Wesley: 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: 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.; 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. 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.