Enumeration of spanning trees on contact graphs of disk packings

Sen Qin, Jingyuan Zhang, Xufeng Chen and Fangyue Chen

Physica A: Statistical Mechanics and its Applications, 2015, vol. 433, issue C, 1-8

Abstract: 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.

Keywords: Spanning tree; Apollonian network; Electrically equivalent network; Entropy (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037843711500309X
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:433:y:2015:i:c:p:1-8

DOI: 10.1016/j.physa.2015.03.047

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().