The asymptotic number of spanning trees in circulant graphs

AbstractLet 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 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s1,i±s2,…,i±sk where all the operations are (modn). We give a closed formula for the asymptotic limit limn→∞T(Cns1,s2,…,sk)1n 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 limn→∞T(Cns1,s2,…,sk,⌊nd1⌋+e1,⌊nd2⌋+e2,…,⌊ndl⌋+el)1n. While this limit does not usually exist, we show that there is some p such that for 0≤q