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

Atajan, Talip; Yong, Xuerong; Inaba, Hiroshi

Discrete Math. 306, No. 22, 2817-2827 (2006).

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.

Reviewer: Peter Kirschenhofer (Leoben)

MSC:

05C30	Enumeration in graph theory
05C05	Trees

Keywords:

spanning tree numbers; circulant graphs

References:

[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