The asymptotic number of spanning trees in circulant graphs |
| |
Authors: | Mordecai J. Golin |
| |
Affiliation: | a Dept. of CSE, Hong Kong UST, Kowloon, Hong Kong b Dept. of Mathematical Sciences, Univ. of Puerto Rico, Mayaguez, United States c School of Computer and Communication, Lanzhou University of Technology, Gansu, PR China |
| |
Abstract: | Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s1,i±s2,…,i±sk where all the operations are . We give a closed formula for the asymptotic limit as a function of s1,s2,…,sk. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting si, di and ei be arbitrary integers, and examining |
| |
Keywords: | Spanning trees Circulant graphs Grids Tori |
本文献已被 ScienceDirect 等数据库收录! |
|