Further analysis of the number of spanning trees in circulant graphs
详细信息 查看全文
- 作者：Talip Atajan ; Xuerong Yong and Hiroshi Inaba
- 关键词：Circulant graphs ; Number of spanning trees ; Recurrence relations ; Asymptotics
- 刊名：Discrete Mathematics
- 出版年：2006
- 出版时间：28 November 2006
- 年：2006
- 卷：306
- 期：22
- 页码：2817-2827
- 全文大小：216 K
文摘
Let 1s1<s2<<skn/2 be given integers. An undirected even-valent circulant graph, has n vertices abed1d344c8e7db0b672"" title=""Click to view the MathML source"">0,1,2,…, n-1, and for each and j (0jn-1) there is an edge between j and . Let stand for the number of spanning trees of . For this special class of graphs, a general and most recent result, which is obtained in [Y.P. Zhang, X. Yong, M. Golin, [The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337–350]], is that where an satisfies a linear recurrence relation of order 2sk-1. And, most recently, for odd-valent circulant graphs, a nice investigation on the number an is [X. Chen, Q. Lin, F. Zhang, The number of spanning trees in odd-valent circulant graphs, Discrete Math. 282 (2004) 69–79].
In this paper, we explore further properties of the numbers an from their combinatorial structures. Comparing with the previous work, the differences are that (1) in finding the coefficients of recurrence formulas for an, we avoid solving a system of linear equations with exponential size, but instead, we give explicit formulas; (2) we find the asymptotic functions and therefore we ‘answer’ the open problem posed in the conclusion of [Y.P. Zhang, X. Yong, M. Golin, The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337–350]. As examples, we describe our technique and the asymptotics of the numbers.