Further analysis of the number of spanning trees in circulant graphs

Let 1 <= s(1) < s(2)<...< S-k <=[n /2] be given integers. An undirected even-valent circulant graph, C-n(s1,s2,...Sk), 0, 1, 2,..., n - 1, and for each s(i) (1 <= i <= k) and j (0 <= j <= n - 1) there is an edge between j and j + s(i) (mod n). Let T(C-n(s1,s2,...,Sk), . For this special class of graphs, a general and most recent result, which is stand for the number of spanning trees of C-n(s1,s2,...Sk), 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 T(C-n(s1,s2,...,Sk)) =na(n)(2) where a(n) satisfies a linear recurrence relation of order 2(sk-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 a(n) from their combinatorial structures. Comparing with the previous work, the differences are that (1) in finding the coefficients of recurrence formulas for a(n), 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. (c) 2006 Published by Elsevier B.V.