Counting the number of spanning trees in a class of double fixed-step loop networks. (English) Zbl 1202.05062

Summary: A double fixed-step loop network, \({\vec C}_n^{p,q}\), is a digraph on \(n\) vertices \(0,1,2,\dots,n-1\) and for each vertex \(i\) (\(0<i\leq n-1\)), there are exactly two arcs going from vertex \(i\) to vertices \(i+p\), \(i+q\) \(\pmod n\). Let \(p<q<n\) be positive integers such that \((q-p)† n\) and \((q-p)|(k_0n-p)\) or \((q-p)|n\) (where \(k_0=\min \{k|(q-p)|(kn-p)\), \(k=1,2,3,\dots\}\) and \(\gcd(q,p)=1\). In this work we derive a formula for the number of spanning trees, \(T({\vec C}_n^{p,q})\), with constant or nonconstant jumps and prove that \(T({\vec C}_n^{p,q})\) can be represented asymptotically by the \(m\)th-order ‘Fibonacci’ numbers. Some special cases give rise to the formulas obtained recently in [Z. Lonc, K. Parol and J.M. Wojciechowski, Networks 37, No. 3, 129–133 (2001; Zbl 0974.05043); X. Yong and F. Zhang, Appl. Math., Ser. B (Engl. Ed.) 12, No. 2, 233–236 (1997; Zbl 0880.05027); Y. Wang, S.-C. Fang and J.E. Lavery, J. Comput. Appl. Math. 201, No. 1, 69–87 (2007; Zbl 1110.65015)].


05C30 Enumeration in graph theory
68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
90C35 Programming involving graphs or networks
Full Text: DOI


[1] Atajan, T.; Yong, X.; Inaba, H., Further analysis of the spanning tree formulas in circulant graphs, Discrete mathematics, 306, 2817-2827, (2006) · Zbl 1131.05048
[2] Erdös, P.; Hsu, D.F., Distributed loop networks with minimum transmission delay, Theoretical computer science, 100, 223-241, (1992) · Zbl 0780.68005
[3] Liu, M.T., Distributed loop computer networks, Advanced in computers, 17, 163-221, (1978)
[4] Yong, X.; Zhang, Y.; Golin, M., The number of spanning trees in a class of double fixed-step loop networks, Networks, 52, 2, 69-87, (2008) · Zbl 1155.05032
[5] Zhang, Y.; Yong, X.; Golin, M., The number of spanning trees in circulant graphs, Discrete mathematics, 223, 337-350, (2000) · Zbl 0969.05036
[6] F.K. Hwang, A survey on double loop networks, in: Proceedings DIMACS Workshop on Reliability of Computer and Communication Networks, 1989
[7] T. Atajan, N. Otsuka, X. Yong, The spanning trees formulas in a class of double fixed-step loop networks, in: The Proceedings of SIAM Workshop on Analytic Algorithmics and Combinatorics, ANALCO09, Jan. 2009, New York City, USA · Zbl 1202.05062
[8] Lonc, Z.; Parol, K.; Wojciechowski, J.M., On the number of spanning trees in directed circulant graphs, Networks, 37, 129-133, (2001) · Zbl 0974.05043
[9] Kirchhoff, G., Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird, Ann. phys. chem., 72, 497-508, (1847)
[10] Baron, G.; Prodinger, H.; Tichy, R.; Boesch, F.; Wang, J., The number of spanning trees in the square of a cycle, The Fibonacci quarterly, 23, 258-264, (1985) · Zbl 0587.05040
[11] Chen, Xiebin, The number of spanning trees in directed circulant graphs with non-fixed jumps, Discrete mathematics, 307, 1873-1880, (2007) · Zbl 1143.05041
[12] Vohra, R.; Washington, L., Counting spanning trees in the graphs of kleitman and Golden and a generalization, Journal of the franklin institute, 318, 349-355, (1984) · Zbl 0569.05016
[13] Yong, X.; Atajan, T., The numbers of spanning trees of the cubic cycle \(C_N^3\) and the quadruple cycle \(C_N^4\), Discrete mathematics, 169, 1-3, 293-298, (1997) · Zbl 0879.05036
[14] Sedgewick, R.; Flajolet, P., An introduction to the analysis of algorithms, (1996), Addison-Wesley Publishing House, and Chebyshev polynomials, Graph and Combinatorics 2 (1986) 191-200
[15] Yong, X.; Zhang, F.J., An asymptotic behavior of the complexity of double fixed step loop networks, Applied mathematics. A journal of Chinese universities. ser. B, 12, 233-236, (1997) · Zbl 0880.05027
[16] Zhang, F.; Yong, X., Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs, Science in China, ser. A, 43, 264-271, (1999) · Zbl 0929.05018
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.