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. View this author's profile
Yong, X.
Zhang, Y.
Issue Date 2010
Source Discrete mathematics , v. 310, (4), 2010, p. 792-803
Summary 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.
Subjects
ISSN 0012-365X
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science
Find@HKUST