Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/57368

# The asymptotic number of spanning trees in circulant graphs

Authors Golin, M.J. Yong, X. Zhang, Y. 2010 Discrete mathematics , v. 310, (4), 2010, p. 792-803 Let T (G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T (G) when G is a circulant graph with given jumps. The circulant graph Cns1, s2, ..., sk is the 2 k-regular graph with n vertices labeled 0, 1, 2, ..., n - 1, where node i has the 2 k neighbors i ± s1, i ± s2, ..., i ± sk where all the operations are (mod n). We give a closed formula for the asymptotic limit limn → ∞ T (Cns1, s2, ..., sk)frac(1, n) as a function of s1, s2, ..., sk. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting si, di and ei be arbitrary integers, and examining under(lim, n → ∞) T (underover(C, n, s1, s2, ..., sk, ⌊ frac(n, d1) ⌋ + e1, ⌊ frac(n, d2) ⌋ + e2, ..., ⌊ frac(n, dl) ⌋ + el))frac(1, n) . While this limit does not usually exist, we show that there is some p such that for 0 ≤ q < p, there exists cq such that limit (1) restricted to only n congruent to q modulo p does exist and is equal to cq. We also give a closed formula for cq. One further consequence of our derivation is that if si go to infinity (in any arbitrary order), then under(lim, s1, s2, ..., sk → ∞) under(lim, n → ∞) T (underover(C, n, s1, s2, ..., sk))frac(1, n) = 4 exp [∫01 ∫01 ⋯ ∫01 ln (underover(∑, i = 1, k) sin2 π xi) d x1 d x2 ⋯ d xk] . Interestingly, this value is the same as the asymptotic number of spanning trees in the k-dimensional square lattice recently obtained by Garcia, Noy and Tejel. © 2009 Elsevier B.V. All rights reserved. 0012-365X English Article View full-text via DOI View full-text via Scopus View full-text via Web of Science