×

The number and degree distribution of spanning trees in the Tower of Hanoi graph. (English) Zbl 1332.05036

Summary: The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the number and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the \(n\)-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.

MSC:

05C05 Trees
05C07 Vertex degrees
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ozeki, K.; Yamashita, T., Spanning trees: a survey, Graphs Combin., 27, 1-26 (2011) · Zbl 1232.05055
[2] 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
[3] Nikolopoulos, S. D.; Palios, L.; Papadopoulos, C., Counting spanning trees using modular decomposition, Theoret. Comput. Sci., 526, 41-57 (2014) · Zbl 1283.05134
[4] Kirchhoff, G. R., Über die Ausflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Ann. Phys. Chem., 72, 497-508 (1847)
[5] Boesch, F. T., On unreliability polynomials and graph connectivity in reliable network synthesis, J. Graph Theory, 10, 339-352 (1986) · Zbl 0699.90041
[6] Colbourn, C. J., The Combinatorics of Network Reliability (1987), Oxford University Press, Inc.
[7] Petingi, L.; Boesch, F.; Suffel, C., On the characterization of graphs with maximum number of spanning trees, Discrete Math., 179, 155-166 (1998) · Zbl 0895.05052
[8] Nishikawa, T.; Motter, A. E., Synchronization is optimal in nondiagonalizable networks, Phys. Rev. E, 73, Article 065106 pp. (2006)
[9] Aldous, D. J., The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math., 3, 450-465 (1990) · Zbl 0717.05028
[10] Brown, T. J.; Mallion, R. B.; Pollak, P.; Roth, A., Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes, Discrete Appl. Math., 67, 51-66 (1996) · Zbl 0846.05087
[11] Godsil, C. D.; Royle, G.; Godsil, C., Algebraic Graph Theory, Graduate Texts in Mathematics (2001), Springer: Springer New York · Zbl 1026.05046
[12] Chaiken, S.; Kleitman, D. J., Matrix tree theorems, J. Combin. Theory Ser. A, 24, 377-381 (1978) · Zbl 0376.05032
[13] Nikolopoulos, S. D.; Papadopoulos, C., The number of spanning trees in \(K_n\)-complements of quasi-threshold graphs, Graphs Combin., 20, 383-397 (2004) · Zbl 1054.05058
[14] Wu, F., Number of spanning trees on a lattice, J. Phys. A: Math. Gen., 10, Article L113 pp. (1977)
[15] 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
[16] Zhang, Z.; Liu, H.; Wu, B.; Zou, T., Spanning trees in a fractal scale-free lattice, Phys. Rev. E, 83, Article 016116 pp. (2011)
[17] Zhang, Z.; Wu, B., Pfaffian orientations and perfect matchings of scale-free networks, Theoret. Comput. Sci., 570, 55-69 (2015) · Zbl 1306.05198
[18] Zhang, Z.; Comellas, F., Farey graphs as models for complex networks, Theoret. Comput. Sci., 412, 865-875 (2011) · Zbl 1206.68245
[19] Zhang, Z.; Wu, B.; Lin, Y., Counting spanning trees in a small-world Farey graph, Phys. A, 391, 3342-3349 (2012)
[20] Yi, Y.; Zhang, Z.; Lin, Y.; Chen, G., Small-world topology can significantly improve the performance of noisy consensus in a complex network, Comput. J., 58, Article bxv014 pp. (2015)
[22] 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
[23] Teufl, E.; Wagner, S., The number of spanning trees in self-similar graphs, Ann. Comb., 15, 355-380 (2011) · Zbl 1234.05123
[24] 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
[25] Aldous, D., Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab., 228-266 (1991) · Zbl 0733.60016
[26] Burton, R.; Pemantle, R., Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab., 1329-1371 (1993) · Zbl 0785.60007
[27] Manna, S. S.; Dhar, D.; Majumdar, S. N., Spanning trees in two dimensions, Phys. Rev. A, 46, Article R4471 pp. (1992)
[28] Chang, S.-C.; Chen, L.-C., Structure of spanning trees on the two-dimensional Sierpiński gasket, Discrete Math. Theor. Comput. Sci., 12, 151-176 (2010) · Zbl 1280.05019
[29] Hinz, A. M.; Klavžar, S.; Milutinović, U.; Petr, C.; Stewart, I., The Tower of Hanoi: Myths and Maths (2013), Springer · Zbl 1285.00003
[30] Dhar, D., Lattices of effectively nonintegral dimensionality, J. Math. Phys., 18, 577-585 (1977)
[31] Dhar, D.; Dhar, A., Distribution of sizes of erased loops for loop-erased random walks, Phys. Rev. E, 55, Article R2093 pp. (1997)
[32] Kneževic, M.; Vannimenus, J., Large-scale properties and collapse transition of branched polymers: exact results on fractal lattices, Phys. Rev. Lett., 56, 1591 (1986)
[33] Zhang, Z.; Wu, B.; Comellas, F., The number of spanning trees in Apollonian networks, Discrete Appl. Math., 169, 206-213 (2014) · Zbl 1288.05066
[34] Wilson, K. G., The renormalization group: critical phenomena and the Kondo problem, Rev. Modern Phys., 47, 773-840 (1975)
[35] Teufl, E.; Wagner, S., Enumeration problems for classes of self-similar graphs, J. Combin. Theory Ser. A, 114, 1254-1277 (2007) · Zbl 1124.05046
[36] Lyons, R., Asymptotic enumeration of spanning trees, Combin. Probab. Comput., 14, 491-522 (2005) · Zbl 1076.05007
[37] Shinoda, M.; Teufl, E.; Wagner, S., Uniform spanning trees on Sierpiński graphs, Lat. Am. J. Probab. Math. Stat., 11, 737-780 (2014) · Zbl 1314.60037
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.