Spanning Trees in a Class of Four Regular Small World Network
Abstract: Spanning tree is 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 four regular network model with small world phenomenon. We introduce the concept and evolving process and determine the relevant topological characteristics of the four regular network, such as diameter and clustering coefficient. We give a calculation method of number of spanning trees in such four 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, of which the entropy is less than the studied network. Thus, the number of spanning trees in such four regular network is more than that of other self-similar networks.
文章引用: 贾环身 , 赵海兴 (2014) 一类四正则小世界网络的生成树数目的算法。 计算机科学与应用， 4， 43-49. doi: 10.12677/CSA.2014.43009
 Zhang, Z.Z., Gao, S.Y., Chen, L.C., Zhou, S.G., Zhang, H.J. and Guan, J.H. (2010) Mapping Koch curves into scalefree small-world networks. Journal of Physics A: Mathematical and Theoretical, 43, Article ID: 395101.
 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 unreliabillity 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, 2093.
 Zhang, Z.Z., Shan, T. and Chen, G.R. (2013) Random walks on weighted networks. Physical Review E, 87, Article ID: 012112.
 Bapat, R.B. (1999) Resistance distance in graphs. The Mathematics Student, 68, 87-98.
 Chang, S.C., Chen, L.C. and Yang, W.S. (2007) Spanning Trees on the Sierpinski Gasket. Journal of Physics, 126, 649.
 Lyons, R., Peled, R. and Schramm, O. (2008) Growth of the number of spanning trees of the Erdős-Rényi giant component. Combinatorics, Probability and Computing, 17, 711.
 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.
 Zhang, Z.Z., Wu, B. and Lin, Y. (2012) Counting spanning trees in a small-world Farey graph. Physica A, 391, 33423349.
 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.
 Bondy, J.A. and Murty, U.S.R. (1976) Graph theory with application. American Elsevier, New York, 10-12.