Enumeration of spanning trees in a pseudofractal scale-free web

Abstract

Spanning trees are an important quantity characterizing the reliability of a network, however, explicitly determining the number of spanning trees in networks is a theoretical challenge. In this paper, we study the number of spanning trees in a small-world scale-free network and obtain the exact expressions. We find that the entropy of spanning trees in the studied network is less than 1, which is in sharp contrast to previous result for the regular lattice with the same average degree, the entropy of which is higher than 1. Thus, the number of spanning trees in the scale-free network is much less than that of the corresponding regular lattice. We present that this difference lies in disparate structure of the two networks. Since scale-free networks are more robust than regular networks under random attack, our result can lead to the counterintuitive conclusion that a network with more spanning trees may be relatively unreliable.

Definitive version accepted for publication in EPL (Europhysics Letters)

References in corpus (13)

• Emergence of scaling in random networks
• Error and attack tolerance of complex networks
• Network robustness and fragility: Percolation on random graphs
• Breakdown of the Internet under intentional attack
• Pseudofractal Scale-free Web
• Synchronization is optimal in non-diagonalizable networks
• Spanning Trees on Graphs and Lattices in d Dimensions
• Spanning trees on the Sierpinski gasket
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Emergence of large cliques in random scale-free network
• Loops of any size and Hamilton cycles in random scale-free networks
• Distribution of sizes of erased loops for loop-erased random walks
• Evolving small-world scale-free networks consist of cliques

Cited by in corpus (11)

• Mapping Koch curves into scale-free small-world networks
• Counting spanning trees in a small-world Farey graph
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Counting spanning trees in self-similar networks by evaluating determinants
• The Number of Spanning Trees of an Infinite Family of Outerplanar, Small-World and Self-Similar Graphs
• Scaling laws for diffusion on (trans)fractal scale-free networks
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Tutte polynomial of pseudofractal scale-free web
• Volatilities analysis of first-passage time and first-return time on a small-world scale-free network
• Spanning Trees of Recursive Scale-Free Graphs
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web