×

Topological properties of a 3-regular small world network. (English) Zbl 1419.05198

Summary: Complex networks have seen much interest from all research fields and have found many potential applications in a variety of areas including natural, social, biological, and engineering technology. The deterministic models for complex networks play an indispensable role in the field of network model. The construction of a network model in a deterministic way not only has important theoretical significance, but also has potential application value. In this paper, we present a class of 3-regular network model with small world phenomenon. We determine its relevant topological characteristics, such as diameter and clustering coefficient. We also give a calculation method of number of spanning trees in the 3-regular network and derive the number and entropy of spanning trees, respectively.

MSC:

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

References:

[1] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 1, 47-97 (2002) · Zbl 1205.82086
[2] Zhang, Z.-Z.; Rong, L.-L.; Comellas, F., Evolving small-world networks with geographical attachment preference, Journal of Physics A: Mathematical and General, 39, 13, 3253-3261 (2006) · Zbl 1088.93003
[3] Wu, F. Y., Number of spanning trees on a lattice, Journal of Physics A: General Physics, 10, 6 (1977)
[4] Shrock, R.; Wu, F. Y., Spanning trees on graphs and lattices in d dimensions, Journal of Physics A: Mathematical and General, 33, 21, 3881-3902 (2000) · Zbl 0949.05041
[5] Bondy, J. A.; Murty, U. S. R., Graph Theory with Applications (1976), New York, NY, USA: American Elsevier, New York, NY, USA · Zbl 1226.05083
[6] Lu, Z.-M.; Guo, S.-Z., A small-world network derived from the deterministic uniform recursive tree, Physica A: Statistical Mechanics and its Applications, 391, 1-2, 87-92 (2012)
[7] Burton, R.; Pemantle, R., Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, The Annals of Probability, 21, 3, 1329-1371 (1993) · Zbl 0785.60007
[8] Lyons, R., Asymptotic enumeration of spanning trees, Combinatorics Probability and Computing, 14, 4, 491-522 (2005) · Zbl 1076.05007
[9] Lyons, R.; Peled, R.; Schramm, O., Growth of the number of spanning trees of the Erdős-Rényi giant component, Combinatorics Probability and Computing, 17, 5, 711-726 (2008) · Zbl 1160.05336
[10] Chang, S.-C.; Chen, L.-C.; Yang, W.-S., Spanning trees on the Sierpinski gasket, Journal of Statistical Physics, 126, 3, 649-667 (2007) · Zbl 1110.82007
[11] Jayakumar, R.; Thulasiraman, K.; Swamy, M. N. S., MOD-CHAR: an implementation of Char’s spanning tree enumeration algorithm and its complexity analysis, IEEE Transactions on Circuits and Systems, 36, 2, 219-228 (1989) · Zbl 0683.68036
[12] Boesch, F. T., On unreliability polynomials and graph connectivity in reliable network synthesis, Journal of Graph Theory, 10, 3, 339-352 (1986) · Zbl 0699.90041
[13] Szabó, G. J.; Alava, M.; Kertész, J., Geometry of minimum spanning trees on scale-free networks, Physica A: Statistical Mechanics and its Applications, 330, 1-2, 31-36 (2003) · Zbl 1027.05024
[14] Nishikawa, T.; Motter, A. E., Synchronization is optimal in nondiagonalizable networks, Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 73, 6 (2006)
[15] Dhar, D.; Dhar, A., Distribution of sizes of erased loops for loop-erased random walks, Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, 55, 3, R2093-R2096 (1997)
[16] Lyons, R., Asymptotic enumeration of spanning trees, Combinatorics Probability and Computing, 14, 4, 491-522 (2005) · Zbl 1076.05007
[17] Zhang, Z. Z.; Gao, S. Y.; Chen, L. C.; Zhou, S. G.; Zhang, H. J.; Guan, J. H., Mapping Koch curves into scale-free small-world networks, Journal of Physics A: Mathematical and Theoretical, 43, 39 (2010) · Zbl 1213.28004
[18] Zhang, Z. Z.; Liu, H. X.; Wu, B.; Zhou, S. G., Enumeration of spanning trees in a pseudofractal scale-free web, Europhysics Letters, 90, 6 (2010)
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.