The asymptotic number of spanning trees in circulant graphs

CORC > 兰州理工大学 > 兰州理工大学

	The asymptotic number of spanning trees in circulant graphs
	Golin, Mordecai J.1; Yong, Xuerong 3; Zhang, Yuanping 2
	2007
会议日期	January 6, 2007 - January 6, 2007
会议地点	New Orleans, LA, United states
关键词	Asymptotic analysis Function evaluation Graph theory Linear systems Number theory Arbitrary integers Asymptotic limits Asymptotic numbers
页码	242-249
英文摘要	Let T(G) be the number of spanning trees in graph G. In this note we explore the asymptotics of T(G) for circulant graphs. The circulant graph C ns1,s2,...,sk is the 2k regular graph with n vertices labelled 0,1,2,... , n - 1, where node i has the 2k neighbors, (0 &le i &le n - 1) adjacent to vertices i + s1,i + S2,...,i + Sk mod n. In this note we give a closed formula for the asymptotic limit limn&rarr∞T(Cns1,s2,...,sk)1/n as a function of s1,s2,..., Sn. We then extend this by permitting the si to be linear functions of n, i.e., we give a closed formula for lim/n&rarr∞ T (Cn s1,s2,...,sk,[n/d1]+e1,[n/d2]+e2,...,[n/d1]+e1)1/n where the di and ei are arbitrary integers. One consequence of our derivation is that if we let the si go to infinity then lim lim s1,s2,...,sk&rarr∞ m&rarr∞ T(Cn s1,s2,...,sk)1/n =4k exp [∫0 1...∫011n(∑i=1 k)dx1dx2...xk] Interestingly, this value is same as the asymptotic number of spanning trees in the k-dirriensional square lattice obtained in Garcia, Noy and Tejel in [7].
会议录	Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
会议录出版者	Society for Industrial and Applied Mathematics Publications, 3600 University City Science Center, Philadelphia, 19104-2688, United States
语种	英语
内容类型	会议论文
源URL	[http://ir.lut.edu.cn/handle/2XXMBERH/117103]
专题	兰州理工大学
作者单位	1.Dept. of Computer Science, Hong Kong UST, ClearWater Bay, Kowloon, Hong Kong; 2.Dept. of Computer and Communications, Lanzhou University of Technology, Lanzhou, 730050, China 3.Department of Mathematics, Univ. of Puerto Rico, Mayaguez, 00681-9018, Puerto Rico;
推荐引用方式 GB/T 7714	Golin, Mordecai J.,Yong, Xuerong,Zhang, Yuanping. The asymptotic number of spanning trees in circulant graphs[C]. 见:. New Orleans, LA, United states. January 6, 2007 - January 6, 2007.