Network reliability analysis by counting the number of spanning trees

In this paper, we consider problems related to the network reliability problem restricted to circulant graphs (networks). Let 1≤s₁2<...k≤[n/2] be given integers. An undirected circulant graph, C_n^s1,s2,...,sk, has n vertices 0, 1, 2, ..., n-1, and for each s_i (1≤i≤k) and j (0≤j≤n-1) there is an edge between j and j+s_i mod n. Let T(C_n^s1,s2,...,sk) stand for the number of spanning trees of C_n^s1,s2,...,sk. For this special class of graphs, a general and most recent result is obtained by Y. P. Zhang et al (Discrete Mathematics vol. 223, pp.337-350, 2000) where it is shown that T(C_n^s1,s2,...,sk)=na_n² where a_n satisfies a linear recurrence relation of order 2^sk-1. In this paper we obtain further properties of the numbers a_n by considering their combinatorial structures. Using these properties we investigate the open problem posed in the Conclusion of Y. P. Zhang et al. We describe our technique and asymptotic properties of the numbers, using examples.