The number of spanning trees in odd valent circulant graphs. (English) Zbl 1042.05051

Chen, Xiebin; Lin, Qiuying; Zhang, Fuji

Discrete Math. 282, No. 1-3, 69-79 (2004).

Summary: We consider the number of spanning trees in circulant graphs. For any class of odd valent circulant graphs \(C_{2n}(a_1,a_2,\dots ,a_{k-1},n)\), where \(a_1,a_2,\dots ,a_{k-1}\) are fixed jumps and \(n\) varies, some formulas, asymptotic behaviors and linear recurrence relations for the number of its spanning trees are obtained, and some known results on the ones in even valent circulant graphs \(C_n(a_1,a_2,\dots ,a_k)\) are improved.

MSC:

05C30	Enumeration in graph theory
05C05	Trees

Keywords:

Spanning tree; Circulant graph; Linear recurrence relation; Asymptotic behavior

References:

[1]	Bermond, J.C; Comellas, F; Hsu, D.F, Distributed loop computer networksa survey, J. parallel distrib. comput., 24, 2-10, (1995)
[2]	Biggs, N, Algebraic graph theory, (1993), Cambridge University Press Cambridge
[3]	Boesch, F.T; Prodinger, H, Spanning tree formulas and Chebyshev polynomials, Graphs combin., 2, 191-200, (1986) · Zbl 0651.05028
[4]	Brualdi, R.A, Introductory combinatorics, (1992), Prentice-Hall Englewood Cliffs, NJ
[5]	Chen, X.B, The numbers of spanning trees in undirected circulant graphs, J. zhangzhou teachers college, 13, 4, 1-6, (2000) · Zbl 0979.05063
[6]	Feng, K.Q; Yu, H.B, Integers and polynomials, (1999), China Higher Education Press Beijing, Springer, Heidelberg, (in Chinese)
[7]	Kleitman, D.J; Golden, B, Counting trees in a certain class of graphs, Amer. math. mon., 82, 40-44, (1975) · Zbl 0297.05123
[8]	X. Li, Z.J. Huang, Enumeration of the Trees in Graphs, and Applications to Reliability of Networks, Harbin University Press, Harbin, 1993 (in Chinese).
[9]	Merris, R, Laplacian matrices of graphsa survey, Linear algebra appl., 197-198, 143-176, (1994) · Zbl 0802.05053
[10]	Yong, X.R; Acenjian, T, The numbers of spanning trees of the cycle CN3 and the quadrupe cycle CN4, Discrete math., 169, 293-298, (1997)
[11]	Zhang, F.J; Yong, X.R, 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
[12]	Zhang, Y; Yong, X; Golin, M.J, The number of spanning trees in circulant graphs, Discrete math., 223, 337-350, (2000) · Zbl 0969.05036