Spanning trees of recursive scale-free graphs

C Tyler Diggans; Erik M Bollt; Daniel Ben-Avraham

doi:10.1103/PhysRevE.105.024312

Spanning trees of recursive scale-free graphs

Phys Rev E. 2022 Feb;105(2-1):024312. doi: 10.1103/PhysRevE.105.024312.

Authors

C Tyler Diggans^{1

2

3}, Erik M Bollt^{1

4}, Daniel Ben-Avraham^{1

2}

Affiliations

¹ Clarkson Center for Complex Systems Science, Clarkson University, Potsdam, New York 13699, USA.
² Department of Physics, Clarkson University, Potsdam, New York 13699, USA.
³ Air Force Research Laboratory: Information Directorate, Rome, New York 13441, USA.
⁴ Department of Electrical and Computer Engineering, Clarkson University, Potsdam, New York 13699, USA.

PMID: 35291180
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 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.