کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423292 1342323 2015 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The formulas for the number of spanning trees in circulant graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 11, 6 November 2015, Pages 1883-1906
نویسندگان
, , , ,