×

The number of spanning trees in Apollonian networks. (English) Zbl 1288.05066

Summary: 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, modular 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 we compare with those of other graphs with the same average degree.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andrade, J. S.; Herrmann, H. J.; Andrade, R. F.S.; da Silva, L. R., Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs, Phys. Rev. Lett., 94, 018702 (2005)
[2] Chang, S.-C.; Chen, L.-C.; Yang, W.-S., Spanning trees on the Sierpiński gasket, J. Stat. Phys., 126, 649-667 (2007) · Zbl 1110.82007
[3] Colbourn, C. J., The Combinatorics of Network Reliability (1987), Oxford University Press: Oxford University Press New York
[4] Dhar, D., Lattices of effectively nonintegral dimensionality, J. Math. Phys., 18, 577-585 (1977)
[5] Doye, J. P.K.; Massen, C. P., Self-similar disk packings as model spatial scale-free networks, Phys. Rev. E, 71, 016128 (2005)
[6] Felker, J. H.; Lyons, R., High-precision entropy values for spanning trees in lattices, J. Phys. A: Math. Gen., 36, 8361-8365 (2003) · Zbl 1099.82503
[7] Godsil, C.; Royle, G., (Algebraic Graph Theory. Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207 (2001), Springer: Springer New York) · Zbl 0968.05002
[8] Huang, Z.-G.; Xu, X.-J.; Wu, Z.-X.; Wang, Y. H., Walks on Apollonian networks, Eur. Phys. J. B, 51, 549-553 (2006)
[9] Kasner, E.; Supnick, F. D., The Apollonian packing of circles, Proc. Natl. Acad. Sci. USA, 29, 378-384 (1943) · Zbl 0063.03162
[10] Knezevic, M.; Vannimenus, J., Large-scale properties and collapse transition of branched polymers: exact results on fractal lattices, Phys. Rev. Lett., 56, 1591 (1986)
[11] Lin, Y.; Wu, B.; Zhang, Z.; Chen, G., Counting spanning trees in self-similar networks by evaluating determinants, J. Math. Phys., 52, 113303 (2011) · Zbl 1272.05187
[12] Lyons, R., Asymptotic enumeration of spanning trees, Combin. Probab. Comput., 14, 491-522 (2005) · Zbl 1076.05007
[13] Marchal, P., Loop-erased random walks, spanning trees and Hamiltonian cycles, Electron. Commun. Probab., 5, 39-50 (2000) · Zbl 0954.60055
[14] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010
[16] Shrock, R.; Wu, F. Y., Spanning trees on graphs and lattices in \(d\) dimensions, J. Phys. A: Math. Gen., 33, 3881 (2000) · Zbl 0949.05041
[17] Solé, R. V.; Valverde, S., Information theory of complex networks: on evolution and architectural constraints, Lecture Notes in Phys., 650, 189-207 (2004) · Zbl 1109.90068
[18] Teufl, E.; Wagner, S., The number of spanning trees of finite Sierpiński graphs, Discrete Math. Theor. Comput. Sci. Proc. AG, 411-414 (2006) · Zbl 1190.05081
[19] Teufl, E.; Wagner, S., Resistance scaling and the number of spanning trees in self-similar lattices, J. Stat. Phys., 142, 879-897 (2011) · Zbl 1213.82024
[20] Tu, Y., How robust is the Internet?, Nature, 406, 353-354 (2000)
[21] Wu, F. Y., Number of spanning trees on a lattice, J. Phys. A: Math. Gen., 10, 113-115 (1977)
[22] Zhang, Z.; Chen, L.; Zhou, S.; Fang, L.; Guan, J.; Zou, T., Analytical solution of average path length for Apollonian networks, Phys. Rev. E, 77, 017102 (2008)
[23] Zhang, Z.; Comellas, F.; Fertin, G.; Rong, L., High dimensional Apollonian networks, J. Phys. A, 39, 1811-1818 (2006) · Zbl 1086.68017
[24] Zhang, Z.; Liu, H.; Wu, B.; Zhou, S., Enumeration of spanning trees in a pseudofractal scale-free web, Europhys. Lett., 90, 68002 (2010)
[25] Zhang, Z.; Liu, H.; Wu, B.; Zou, T., Spanning trees in a fractal scale-free lattice, Phys. Rev. E, 83, 016116 (2011)
[26] Zhang, Z.; Rong, L.; Comellas, F., High dimensional random Apollonian networks, Physica A, 364, 610-618 (2005)
[27] Zhang, Z.; Rong, L.; Zhou, S. G., Evolving Apollonian networks with small-world scale-free topologies, Phys. Rev. E, 74, 046105 (2006)
[28] Zhang, Z.; Zhou, S., Correlations in random Apollonian networks, Physica A, 380, 621-628 (2007)
[29] Zhou, T.; Yan, G.; Wang, B. H., Maximal planar networks with large clustering coefficient and power-law degree distribution, Phys. Rev. E, 71, 046141 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.