کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423292 | 1342323 | 2015 | 24 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The formulas for the number of spanning trees in circulant graphs The formulas for the number of spanning trees in circulant graphs](/preview/png/6423292.png)
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).
Journal: Discrete Mathematics - Volume 338, Issue 11, 6 November 2015, Pages 1883-1906