×

Correct proof of the main result in “The number of spanning trees of a class of self-similar fractal models” by Ma and Yao. (English) Zbl 1512.05194

Summary: The problem of counting the number of spanning trees of a network built by a replacement procedure that yields a self-similar structure is considered. This problem has been receiving growing attention in the specialized literature in the recent years. One of the important measures of the global reliability of a network is the number of spanning trees. In this paper, we present a correction of the two main theorems claimed by F. Ma and B. Yao [Inf. Process. Lett. 136, 64–69 (2018; Zbl 1476.05084)] concerning the number and the entropy of spanning trees of a class of self-similar fractal models with proofs of the new results. Also, the numerical values of the number of spanning trees are obtained and compared with the values of the formula in Theorem 3.1 of [loc. cit.].

MSC:

05C30 Enumeration in graph theory
05C05 Trees
05C82 Small world graphs, complex networks (graph-theoretic aspects)
28A80 Fractals
90B10 Deterministic network models in operations research

Citations:

Zbl 1476.05084
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anema, J.; Tsougkas, K., Counting spanning trees on fractal graphs and their asymptotic complexity, J. Phys. A, Math. Theor., 49, 35, Article 355101 pp. (2016) · Zbl 1350.05141
[2] Burton, R.; Pemantle, R., Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab., 21, 1329-1371 (1993) · Zbl 0785.60007
[3] Comellas, F.; Miralles, A.; Liu, H.; Zhang, Z., The number of spanning trees of an infinite family of outerplanar, small-world and self-similar graphs, Physica A, 392, 2803-2806 (2013) · Zbl 1395.05157
[4] El Atik, A. A.; Nasef, A. A., Some topological structures of fractals and their related graphs, Filomat, 34, 1, 1-24 (2020)
[5] Lin, Y.; Wu, B.; Zhang, Z.; Chen, G., Counting spanning trees in self-similar networks by evaluating determinants, J. Math. Phys., 52, Article 113303 pp. (2011) · Zbl 1272.05187
[6] Lyons, R., Asymptotic enumeration of spanning trees, Comb. Probab. Comput., 12, 491-522 (2005) · Zbl 1076.05007
[7] Ma, F.; Yao, B., The number of spanning trees of a class of self-similar fractal models, Inf. Process. Lett., 136, 64-69 (2018) · Zbl 1476.05084
[8] Ma, F.; Su, J.; Hao, Y.; Yao, B.; Yan, G., A class of vertex edge-growth small-world network models having scale-free, self-similar and hierarchical characters, Physica A, 492, 1194-1205 (2018)
[9] Ma, F.; Yao, B., An iteration method for computing the total number of spanning trees and its applications in graph theory, Theor. Comput. Sci., 708, 46-57 (2018) · Zbl 1383.05054
[10] Mokhlissi, R.; Lotfi, D.; Debnath, J.; El Marraki, M.; EL Khattabi, N., The evaluation of the number and the entropy of spanning trees on generalized small-world networks, J. Appl. Math., 2018 (2018) · Zbl 1437.05048
[11] Teufl, E.; Wagner, S., Enumeration problems for classes of self-similar graphs, J. Comb. Theory, Ser. A, 114, 1254-1277 (2007) · Zbl 1124.05046
[12] Teufl, E.; Wagner, S., The number of spanning trees in self-similar graphs, Ann. Comb., 15, 355-380 (2011) · Zbl 1234.05123
[13] West, D., Introduction to Graph Theory, Pearson Modern Classic for Advanced Mathematics Series (2017), New York
[14] Xiao, Y.; Zhao, H., New method for counting the number of spanning trees in a two-tree network, Physica A, 392, 4576-4583 (2013) · Zbl 1395.05174
[15] Zhang, Z. Z.; Wu, B.; Comellas, F., The number of spanning trees of Apollonian networks, Discrete Appl. Math., 169, 206-213 (2014) · Zbl 1288.05066
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.