×

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.

MSC:

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

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 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: Prentice-Hall Englewood Cliffs, NJ · Zbl 0734.05001
[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: 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).; 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 \(C_N^3\) and the quadrupe cycle \(C_N^4\), Discrete Math., 169, 293-298 (1997) · Zbl 0879.05036
[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. 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.