The number of spanning trees in a class of double fixed-step loop networks. (English) Zbl 1155.05032

Summary: We develop a method to count the number of spanning trees in certain classes of double fixed-step loop networks with nonconstant steps. More specifically our technique finds the number of spanning trees in \(\vec C_n^{p,q}\), the double fixed-step loop network with \(n\) vertices and jumps of size \(p\) and \(q\), when \(n = d_{1}m\), and \(q = d_{2}m + p\) where \(d_{1}\), \(d_{2}\), and \(p\) are arbitrary parameters and \(m\) is a variable.


05C20 Directed graphs (digraphs), tournaments
05C05 Trees
05C30 Enumeration in graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Bermond, Distributed loop computer networks: A survey, J Parallel Distrib Comput 24 pp 2– (1995)
[2] Biggs, Algebraic graph theory (1993) · Zbl 0284.05101
[3] Boesch, Spanning tree formulas and Chebyshev polynomials, Graph Combinatorics 2 pp 191– (1986) · Zbl 0651.05028
[4] Cvetkovič, Spectra of graphs: Theory and applications (1995)
[5] Erdös, Distributed loop networks with minimum transmission delay, Theoret Comput Sci 100 pp 223– (1992)
[6] Fàbrega, Fault-tolerant routings in double fixed-step networks, Discrete Appl Math 78 pp 61– (1997) · Zbl 0890.68099
[7] Golin, Counting spanning trees and other structures in non constant-jump circulant graphs, 15th Annu Int Symp Algorithms and Computation pp 508– (2004) · Zbl 1116.05303 · doi:10.1007/978-3-540-30551-4_45
[8] Harary, Graph theory (1969)
[9] Hwang, A survey on double loop networks, Proc DIMACS Workshop on Reliability of Computer and Communication Networks pp 143– (1989)
[10] Jennings, First course in numerical methods (1964) · Zbl 0127.08102
[11] Kirchhoff, Ü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 pp 497– (1847)
[12] Liu, Distributed loop computer networks, Adv Comput 17 pp 163– (1978) · doi:10.1016/S0065-2458(08)60392-7
[13] Lonc, On the number of spanning trees in directed circulant graphs, Networks 37 pp 129– (2001) · Zbl 0974.05043
[14] Vohra, Counting spanning trees in the graphs of Kleitman and Golden and a generalization, J Franklin Inst 318 pp 349– (1984) · Zbl 0569.05016
[15] Yong, An asymptotic behavior of the complexity of double fixed step loop networks, Appl Math J Chinese Univ Ser B 12 pp 233– (1997)
[16] Zhang, Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs, Sci China Ser A 43 pp 264– (1999)
[17] Zhang, The number of spanning trees in circulant graphs, Discrete Math 223 pp 337– (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.