Enumeration and Applications of Spanning Trees in Book Networks with Common Path

The spanning trees number of a network, also known as the complexity of a network is an essential measure characterizing the network reliability and its availability. In this paper, we enumerate the spanning trees of a book network with a common path. We propose two combinatorial methods to calculate the spanning trees number of this network. We present two types of the book network: A book network having the same number of vertices in each cycle and a book network with different number of vertices in each cycle. For the first type of book network, we propose the geometrical transformation approaches which are the bipartition and the reduction that make the enumeration of spanning trees of a large network (containing a large number of vertices and edges) easy to calculate. For the second type of a book network, we use the generalization of Fussner Theorem to find its complexity whatever its size. Finally, we give the spanning trees number of some networks derived from our two book networks, such as a chain and a closed chain. As an application in computer networking, we give a formula to estimate the reliability of our network.