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

Yong, Xuerong; Zhang, Yuanping; Golin, Mordecai J.

Networks 52, No. 2, 69-77 (2008).

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.

MSC:

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

Keywords:

circulant digraph; spanning tree; matrix tree theorem; double loop network; step loop network; step double loop network

References:

[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
[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)
[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