Spanning Trees of Recursive Scale-Free Graphs
arXiv:2112.07325 · doi:10.1103/PhysRevE.105.024312
Abstract
We present a link-by-link rule-based method for constructing all members of the ensemble of spanning trees for any recursively generated, finitely articulated graph, such as the DGM net. The recursions allow for many large-scale properties of the ensemble of spanning trees to be analytically solved exactly. We show how a judicious application of the prescribed growth rules selects for certain subsets of the spanning trees with particular desired properties (small-world or extended diameter, degree distribution, etc.), and thus provides solutions to several optimization problems. The analysis of spanning trees enhances the usefulness of recursive graphs as sophisticated models for everyday life complex networks.
arXiv commentAccepted to PRE, ref will be updated once available
References in corpus (13)
- Pseudofractal Scale-free Web
- Fractal and Transfractal Recursive Scale-Free Nets
- Scale-free trees: the skeletons of complex networks
- Percolation in Hierarchical Scale-Free Nets
- On the spectrum of the normalized Laplacian of iterated triangulations of graphs
- Enumeration of spanning trees in a pseudofractal scale-free web
- A general geometric growth model for pseudofractal scale-free web
- Statistics of Cycles: How Loopy is your Network?
- Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
- Stochastic and mixed flower graphs
- The Use of Minimal Spanning Trees in Particle Physics
- Globally optimal dense and sparse spanning trees, and their applications
- The Essential Synchronization Backbone Problem