The Number of Spanning Trees in Apollonian Networks

Abstract

In this paper we find an exact analytical expression for the number of spanning trees in Apollonian networks. This parameter can be related to significant topological and dynamic properties of the networks, including percolation, epidemic spreading, synchronization, and random walks. As Apollonian networks constitute an interesting family of maximal planar graphs which are simultaneously small-world, scale-free, Euclidean and space filling and highly clustered, the study of their spanning trees is of particular relevance. Our results allow also the calculation of the spanning tree entropy of Apollonian networks, which then we compare with those of other graphs with the same average degree.

Manuscript accepted for publication (Discrete Applied Mathematics)

References in corpus (10)

• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Self-similar disk packings as model spatial scale-free networks
• Spanning trees on the Sierpinski gasket
• High dimensional random Apollonian networks
• Evolving Apollonian Networks with Small-world Scale-free topologies
• Exact analytical solution of average path length for Apollonian networks
• Correlations in random Apollonian network
• Modelling the brain as a n Apollonian network