Counting the number of spanning trees in a class of double fixed-step loop networks

✍ Scribed by Talip Atajan; Naohisa Otsuka; Xuerong Yong

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 495 KB
• Volume: 23
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2009.04.006

✦ Synopsis

A double fixed-step loop network, C p,q n , is a digraph on n vertices 0, 1, 2, . . . , n -1 and for each vertex i (0 < i ≤ n-1), there are exactly two arcs going from vertex i to vertices i+p, i + q (mod n). Let p < q < n be positive integers such that (qp) Ď n and (qp)|(k 0 np) or (qp)|n (where k 0 = min{k|(qp)|(knp), k = 1, 2, 3, . . .} and gcd(q, p) = 1. In this work we derive a formula for the number of spanning trees, T ( C p,q n ), with constant or nonconstant jumps and prove that T ( C p,q n ) can be represented asymptotically by the mthorder 'Fibonacci' numbers. Some special cases give rise to the formulas obtained recently in [Z. Lonc, K.