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 2s−12s−1 where ss is the largest jump [29]. A drawback here is that, when the jump ss 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±CG=Kn±C, where KnKn is the complete graph on nn vertices and CC is a circulant graph. Compared with the previous approaches, our advantage is that, for any given jumps s1