The asymptotic number of spanning trees in circulant graphs

Let T(G)T(G) be the number of spanning trees in graph GG. In this note, we explore the asymptotics of T(G)T(G) when GG is a circulant graph with given jumps.The circulant graph Cns1,s2,…,sk is the 2k2k-regular graph with nn vertices labeled 0,1,2,…,n−10,1,2,…,n−1, where node ii has the 2k2k neighbors i±s1,i±s2,…,i±ski±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,…,sks1,s2,…,sk. We then extend this by permitting some of the jumps to be linear functions of nn, i.e., letting sisi, didi and eiei 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 pp such that for 0≤q