×

The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. (English) Zbl 1395.05157

Summary: In this paper we give an exact analytical expression for the number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs. This number is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion properties. The calculation of the number of spanning trees is a demanding and difficult task, in particular for large graphs, and thus there is much interest in obtaining closed expressions for relevant infinite graph families. We have also calculated the spanning tree entropy of the graphs which we have compared with those for graphs with the same average degree.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Colbourn, C. J., The combinatorics of network reliability, (1987), Oxford University Press New York
[2] Takashi, N.; Motter, A. E., Synchronization is optimal in nondiagonalizable networks, Phys. Rev. E, 73, 065106(R), (2006)
[3] Marchal, P., Loop-erased random walks, spanning trees and Hamiltonian cycles, Electron. Commun. Probab., 5, 39-50, (2000) · Zbl 0954.60055
[4] Godsil, C.; Royle, G., (Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, (2001), Springer New York) · Zbl 0968.05002
[5] Nikolopoulos, S. D.; Papadopoulos, C., The number of spanning trees in kn-complements of quasi-threshold graphs, Graphs Combin., 20, 383-394, (2004) · Zbl 1054.05058
[6] 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
[7] Chang, S.-C.; Chen, L.-C.; Yang, W.-S., Spanning trees on the sierpinski gasket, J. Stat. Phys., 126, 649-667, (2007) · Zbl 1110.82007
[8] 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
[9] Comellas, F.; Miralles, A., Modeling complex networks with self-similar outerplanar unclustered graphs, Physica A, 388, 2227-2233, (2009)
[10] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256, (2003) · Zbl 1029.68010
[11] Ferrer i Cancho, R.; Janssen, C.; Solé, R. V., Topology of technology graphs: small world patterns in electronic circuits, Phys. Rev. E, 64, 046119, (2001)
[12] Brandstaedt, A.; Le, V. B.; Spinrad, P. J., (Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, (1999), SIAM Philadelphia, PA)
[13] Comellas, F.; Miralles, A., Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks, J. Phys. A: Math. Gen., 42, 425001, (2009) · Zbl 1180.90032
[14] Knezevic, M.; Vannimenus, J., Large-scale properties and collapse transition of branched polymers: exact results on fractal lattices, Phys. Rev. Lett., 56, 1591, (1986)
[15] Zhang, Z.; Liu, H.; Wu, B.; Zhou, S., Enumeration of spanning trees in a pseudofractal scale-free web, Europhys. Lett., 90, 68002, (2010)
[16] Zhang, Z.; Liu, H.; Wu, B.; Zou, T., Spanning trees in a fractal scale-free lattice, Phys. Rev. E, 83, 016116, (2011)
[17] Lyons, R., Asymptotic enumeration of spanning trees, Combin. Probab. Comput., 14, 491-522, (2005) · Zbl 1076.05007
[18] Wu, F. Y., Number of spanning trees on a lattice, J. Phys. A: Math. Gen., 10, 113-115, (1977)
[19] Z. Zhang, M. Li, S. Wu, F. Comellas, The number and structure of spanning trees in the Hanoi graph (submitted for publication). · Zbl 1332.05036
[20] Tu, Y., How robust is the Internet?, Nature, 406, 353-354, (2000)
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.