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

Chen, Xiebin

Discrete Math. 307, No. 15, 1873-1880 (2007).

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)\).

Reviewer: Ulrich Knauer (Oldenburg)

MSC:

05C30	Enumeration in graph theory
05C05	Trees

Keywords:

spanning tree; directed circulant graph; linear recurrence relation; asymptotic behavior

References:

[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
[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 · 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 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, (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