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

The 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 2 s − 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. s 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 = K n ± C , where K n 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 s 1 < s 2 < ⋯ < s k , the number of spanning trees can be calculated directly by a new kind of recursive formula, without establishing the recurrence relation of order 2 s k − 1 . We describe our method by giving concrete examples of its use.