Enumeration of spanning trees on contact graphs of disk packings

Obtaining the number of spanning trees of complex networks is an outstanding challenge, since traditional approaches, such as calculating the eigenvalues of the matrix and decomposing of spanning subgraphs, are awkward or even infeasible for a large scale network. The foundation and importance of this quantity relating to some topological and dynamic properties prompt us to explore the role of determinant identities for Laplace matrices. We introduce the basic electrically equivalent technique to determine an exact analytical expression for the quantity on the contact graph of disk packings, which is proposed by Zhang et al. (2009). Our theoretical results shed light on the relationship between the microscopic change of the quantity and topological iteration of the network. In particular, we compare the entropy of spanning trees on the network with the other two-dimensional and three-dimensional lattices. We show that the new model is a small-world scale-free network with the maximum entropy so far found. In addition, our method for employing the electrically equivalent technique to enumerate spanning trees is general and can be easily extended to other complex networks.