The formulas for the number of spanning trees in circulant graphs

The circulant graph Cns1,s2,…,st is the 2t regular graph with n vertices labeled 0,1,2,…,n−1, where each vertex i has the 2t neighbors i±s1,i±s2,…,i±st in which all the operations are modulo n. Golin et al. (2010) derive several closed integral formulas for the asymptotic limitlimn→∞T(Cns1,s2,…,sk,⌊nd1⌋+e1,⌊nd2⌋+e2,…,⌊ndl⌋+el)1n, as a function of si, dj and ek, where T(G) is the number of spanning trees in graph G.In this paper we derive simple and explicit formulas for the number of spanning trees in circulant graphs Cpn1,a1n,a2n,…,aln. Following from the formulas we show that limn→∞T(Cpn1,a1n,a2n,…,aln)1n=∏t=0k−1(1+∑i=1lsin2πaitp+∑i=1lsin2πaitp)2pk, where k=lcm(pa1,pa2,…,pal), and lcm denotes the least common multiple. The asymptotic limit represents the average growth rate of the number of spanning trees.The research is continuation of the previous work (Golin et al., 2010; Zhang et al., 2000; Zhang et al., 2005).