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

A double fixed-step loop network, C → n p , q , 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 ( q − p ) † n and ( q − p ) | ( k 0 n − p ) or ( q − p ) | n (where k 0 = m i n { k | ( q − p ) | ( k n − p ) , k = 1 , 2 , 3 , … } and g c d ( q , p ) = 1 . In this work we derive a formula for the number of spanning trees, T ( C → n p , q ) , with constant or nonconstant jumps and prove that T ( 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, J.M. Wojciechowski, On the number of spanning trees in directed circulant graphs, Networks 37 (2001) 129–133; X. Yong, F.J. Zhang, An asymptotic behavior of the complexity of double fixed step loop networks, Applied Mathematics. A Journal of Chinese Universities. Ser. B 12 (1997) 233–236; X. Yong, Y. Zhang, M. Golin, The number of spanning trees in a class of double fixed-step loop networks, Networks 52 (2) (2008) 69–87].