On The Number Of Spanning Trees And Its Asymptotics Of A Class Of Undirected Graphs

The study of the number of spanning trees in a graph has a long history in graph theory. It has extensive practical applications in many fields, e.g., analyzing the reliability of a network, designing electrical circuits in physics, etc.[6,10,14]. So it has an important theoretical and practical significance to study the number of spanning trees and its asymptotics.In this paper, we focus on the number of spanning trees and its asymptotics of undirected circulant graphs, which have been received much attention in the last decades[2,8,13,27,28]. We mainly discuss the equations between the number of spanning trees and parameters of undirected circulant graphs, and make a deeply study of the properties of the number of spanning trees.First, we derive simple and explicit formulas for the number of spanning trees in aforesaid circulant graphs, which realize the calculation of the number of spanning trees from some simple parameters of graphs, and improve calculation methods of the number. Second, we analyze the asymptotics of the number of spanning trees, and obtain the formula for the asymptotic value of the number of spanning trees, where are integers, and, denotes the least common multiple. The asymptotic limit represents the average growth rate of the mumber of spanning trees[13]. And then the average growth rate of the mumber of spanning trees in this class of circulant graphs can be calculated precisely, which overcome the disadvantage that it is not easy to directly count the exact number from formerly formulas, and widely simplify the calculation to a great extent, hence it is convenient for application.Last, we consider the max and the min value of the asymptotic value of the number of spanning trees and prove the value has monotonic increasing property, and further depict the properties of the number of spanning trees in this class of circulant graphs, which has theoretical and practical value.