New method for counting the number of spanning trees in a two-tree network

Yuzhi Xiao and Haixing Zhao

Physica A: Statistical Mechanics and its Applications, 2013, vol. 392, issue 19, 4576-4583

Abstract: The number of spanning trees is an important quantity characterizing the reliability of a network. Generally, the number of spanning trees in a network can be obtained by directly calculating a related determinant corresponding to the network. However, for a large network, evaluating the relevant determinant is intractable. In this paper, we investigate the number of spanning trees in two-tree networks. We first give a new algorithm which avoids the laborious computation of the determinant for counting the number of spanning trees. Using the algorithm, we can obtain the number of spanning trees of any two-tree network in linear time. The result shows that the computation complexity is O(n), which is better than that of the matrix tree theorem with O(n2), where n is the number of steps. We then characterize two-tree networks with the maximum and minimum numbers of spanning trees. Denote by P(t) and K(t), respectively, the two-tree networks of t+2 vertices with the maximum and minimum numbers of spanning trees. Denote by PA and EN, respectively, the two-tree network of t+2 vertices generated by preferential attachment and by equiprobability attachment. By algorithmic analysis and through simulations, we conjecture that NST(K(t))≤NST(PA)≤NST(EN)≤NST(P(t)) as t tends to infinity, where NST(G) is the number of spanning trees of G. As an application of the algorithm, we give the formula of the number of spanning trees of a particular small-world network.

Keywords: Complex network; The number of spanning trees; Two-tree (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437113004123
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:392:y:2013:i:19:p:4576-4583

DOI: 10.1016/j.physa.2013.05.007

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 ().