The number of spanning trees in directed circulant graphs with non-fixed jumps. (English) Zbl 1143.05041

The phrase “non-fixed jumps” in the title is somewhat misleading. The author apparently has in mind that the formulas depend on the integer \(n\) which controls the jumps. For example there is given a formula for the number of trees of the circulant graph \(C_{pn}(a_1,\dots,a_k, q_1n,\dots,q_mn)\) using a formula for \(C_n(a_1,\dots,a_k)\) and other functions depending on \(n\). Similarly asymptotic behaviours and linear recurrence relations are considered for this problem. In 10 examples the formulas are evaluated for graphs of the form \(C_{kn}(1,rn)\) with \(k=2,3,4,5,6\) and \(r= 1,2,3,5\) and for \(C_{2n}(1,2,n)\).


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


[1] Bermond, J. C.; Comellas, F.; Hsu, D. F., Distributed loop computer networks: a survey, J. Parallel Distribution 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 Coll., 13, 4, 1-6 (2000) · Zbl 0979.05063
[6] Chen, X. B.; Lin, Q. Y.; Zhang, F. J., The number of spanning trees in odd valent circulant graphs, Discrete Math., 282, 69-79 (2004) · Zbl 1042.05051
[7] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[8] Li, X.; Huang, Z. J., Enumeration of the Trees in Graphs, and Applications to Reliability of Networks (1993), Harbin University Press: Harbin University Press Harbin, (in Chinese)
[9] 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
[10] Zhang, F. J.; Yong, X. R., Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraph & graphs, Sci. China Ser. A, 43, 2, 264-271 (1999) · Zbl 0929.05018
[11] 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.