An efficient approach for counting the number of spanning trees in circulant and related graphs

AbstractThe most recent general result for counting the exact number of spanning trees in a directed or an undirected circulant graph is that the numbers satisfy a recurrence relation of size 2s−1 where s is the largest jump [29]. A drawback here is that, when the jump s is large, it is difficult to apply the method to get the number of spanning trees because the degree of the recurrence relation grows exponentially and the coefficient matrix (it is an integral Toeplitz matrix of exponential size) of the linear system for establishing recurrence formula is not well conditioned in calculation.In this paper, we focus our attention on this point and obtain an efficient approach (another kind of recursive formula) for counting the number of spanning trees in a directed or undirected circulant graph which has fixed or non-fixed jumps. The technique is also applied to the graphs G=Kn±C, where Kn is the complete graph on n vertices and C is a circulant graph. Compared with the previous approaches, our advantage is that, for any given jumps s1<s2<⋯