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

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.


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


[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
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.