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

详细信息    查看全文

• 作者：Talip Atajan ; Naohisa Otsuka ; Xuerong Yong
• 刊名：Applied Mathematics Letters
• 出版年：2010
• 出版时间：March 2010
• 年：2010
• 卷：23
• 期：3
• 页码：291-298
• 全文大小：495 K

文摘

A double fixed-step loop network, , is a digraph on n vertices 0,1,2,…,n−1 and for each vertex , there are exactly two arcs going from vertex i to vertices . Let p<q<n be positive integers such that (q−p)†n and (q−p)(k₀n−p) or (q−p)n (where k₀=min{k(q−p)(kn−p),k=1,2,3,…} and gcd(q,p)=1. In this work we derive a formula for the number of spanning trees, , with constant or nonconstant jumps and prove that can be represented asymptotically by the mth-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].