Spanning trees of recursive scale-free graphs.

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 Dorogovtsev-Goltsev-Mendes (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, extended diameter, degree distribution, etc.), and thus approximates and/or provides solutions to several optimization problems on undirected and unweighted networks. The analysis of spanning trees enhances the usefulness of recursive graphs as sophisticated models for everyday life complex networks.