Spanning Trees in a Class of Five Regular Small World Network
Abstract: Spanning trees are an important quantity characterizing the reliability of a network, however, explicitly determining the number of spanning trees in networks is a theoretical challenge. In this paper, we present a class of five regular network model with small world phenomenon, and introduce the concept and evolving process. We determine the relevant topological characteristics of the five regular network, such as diameter, clustering coefficient. We give a calculation method of number of spanning trees in such five regular network and derive the formulas and the entropy of number of spanning trees. We find that the entropy of spanning trees in the studied network is in sharp contrast to other small world with the same average degree, the entropy of which is less than the studied network. Thus, the number of spanning trees in such five regular network is more than that of other self-similar networks.
文章引用: 贾环身 , 吴廷增 (2017) 一类五正则小世界网络模型的生成树数目的算法。 理论数学， 7， 401-407. doi: 10.12677/PM.2017.75052
Zhang, Z.Z., Liu, H.X., Wu, B. and Zou, T. (2011) Spanning Trees in a Fractal Scale-Free Lattice. Physical Review E, 83, Article ID: 016116.
Boesch, F.T. (1986) On Unreliability Polynomials and Graph Connectivity in Reliable Network Synthesis. Journal of Graph Theory, 10, 339-352.
Nishikawa, T. and Motter, A.E. (2006) Synchronization Is Optimal in Non-Diagonalizable Networks. Physical Review E, 73, Article ID: 065106.
 Noh, J.D. and Rieger, H. (2003) Random Walks on Complex Networks. Physical Review, 92, Article ID: 118701.
Dhar, D. and Dhar, A. (1997) Distribution of Sizes of Erased Loops for Loop-Erased Random Walks. Physical Review E, 55, R2093.
 Bapat, R.B. (1999) Resistance Distance in Graphs. The Mathematics Student, 68, 87-98.
Wu, F.-Y. (1977) Number of Spanning Trees on a Lattice. Journal of Physics A, 10, 113-115.
Chang, S.C., Chen, L.C. and Yang, W.S. (2007) Spanning Trees on the Sierpinski Gasket. Journal of Physics, 126, 649-667.
Zhang, Z.Z., Liu, H.X., Wu, B. and Zhou, S.G. (2010) Enumeration of Spanning Tree in a Pseudofractal Scale-Free Web. Europhysics Letters, 90, Article ID: 68002.
Hu, G.N., Xiao, Y.Z., Jia, H.S. and Zhao, H.X. (2013) A New Class of the Planar Networks with High Clustering and High Entropy. Abstract and Applied Analysis, 2013, Article ID: 795682.
Xiao, Y.Z. and Zhao, H.X. (2013) New Method for Counting the Number of Spanning Trees in a Two -Tree Network. Physica A: Statistical Mechanics and Its Applications, 392, 4576-4583.
 Jia, H.S. and Zhao, H.X. (2014) Spanning Trees in a Class of Four Regular Small World Network. Computer Science and Application, 4, Article ID: 13291.
 Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Application. American Elsevier, New York, 10-12.
Lin, Y., Wu, B., Zhang, Z.Z., et al. (2011) Counting Spanning Trees in Self-Similar Networks by Evaluating Determinants. Journal of Mathematical Physics, 52, Article ID: 113303.