基于电网络技巧计数一类平面自相似图的生成树数目

doi:10.15960/j.cnki.issn.1007-6093.2022.04.010

Abstract

Abstract: The Sierpiński gasket pyramid networks are the sketches of the Sierpiński tetrahedra which are the three-dimensional analogue of the Sierpiński triangles. Motivated by the construction of Sierpiński gasket pyramid networks, in this work we study the spanning trees of a new class of self-similar planar networks which has a very similar iterative generating method. By using the self-similarity and employing techniques from electrical networks, we obtain the exact analytical expression for the number of spanning trees of this kind of planar networks as well as the entropy of spanning trees.

Key words: Sierpiński triangle, spanning tree, self-similar, electrically equivalent, entropy

CLC Number:

O157.5

ZHAO Weiliang, QI Linming. Counting the spanning trees for a class of self-similar planar graphs based on techniques from electrical networks[J]. Operations Research Transactions, 2022, 26(4): 119-126.

References

[1] Cvetković D, Doob M, Sachs H. Spectra of Graphs: Theorey and Application[M]. New York: Academic Press, 1980: 218.
[2] Tutte W T. Codichromatic graphs[J]. Journal of Combinatorial Theory, Series B, 1974, 16: 168-174.
[3] Jacobsen J L, Salas J, Sokal A D. Spanning forests and the q-state Potts model in the limit q → 0[J]. Journal of Statistical Physics, 2005, 115: 1153-1281.
[4] Colbourn C J. The Combinatorics of Network Reliability[M]. Oxford: Oxford University Press, 1987.
[5] Beosch F T. On unreliability polynomials and graph connectivity in reliable network synthesis [J]. Journal of Graph Theory, 1986, 3: 339-352.
[6] Macdonald P J, Almaas E, Barabási A L. Minimum spanning trees of weighted scale-free networks[J]. Europhysics Letters, 2005, 72: 308-314.
[7] Teufl E, Wagner S. Determinant identities for Laplace matrices[J]. Linear Algebra and Its Applications, 2010, 432: 441-457.
[8] Marchal P. Loop-erased random walks, spanning trees and hamiltonian cycles[J]. Electronic Communications in Probability, 2000, 5: 39-50.
[9] Dhar D, Dhar A. Distribution of sizes of erased loops for loop-erased random walks[J]. Physical Review E, 1997, 55: R2093-R2096.
[10] Teufl E, Wagner S. Resistance scaling and the number of spanning trees in self-similar lattices [J]. Journal of Statistical Physics, 2011, 142: 879-897.
[11] Kirchhoff G. Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird[J]. Annual Review of Physical Chemistry, 1847, 72: 497-508.
[12] Lyons R. Asymptotic enumeration of spanning trees[J]. Combinatorics Probability & Computing, 2005, 14: 491-522.
[13] Qin S, Zhang J Y, Chen X, et al. Enumeration of spanning trees on contact graphs of disk packings[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 433: 1-8.
[14] Shrock R, Wu F. Spanning trees on graphs and lattices in d dimensions[J]. Journal of Physics A: General Physics, 2000, 33: 3881-3902.
[15] Yan W G. Enumeration of spanning trees of graphs with rotational symmetry[J]. Journal of Combinatorial Theory, Series A, 2011, 118: 1270-1290.
[16] Zhang Y P, Yong X R, Golin M J. Chebyshev polynomials and spanning tree formulas for circulant and related graphs[J]. Discrete Mathematics, 2005, 298: 334-364.
[17] Song C M, Havlin S, Makse H A. Self-similarity of complex networks[J]. Nature, 2005, 433: 392-395.
[18] Chang S C, Chen L C, Yang W S. Spanning trees on the Sierpiński gasket[J]. Journal of Statistical Physics, 2007, 126: 649-667.
[19] William A, Rajasingh I, Rajan B, et al. Topological properties of Sierpiński gasket pyramid network[C]//Proceeding of Informatics Engineering and Information Science, Kuala Lumpur: Springer, 2011: 431-439.
[20] Zhang Z Z, Wu B, Comellas F. The number of spanning trees in apollonian networks[J]. Discrete Applied Mathematics, 2014, 169: 206-213.
[21] Gong H L, Jin X A. A general method for computing Tutte polynomials of self-similar graphs [J]. Physica A: Statistical Mechanics and Its Applications, 2017, 83: 117-129.
[22] Zhang Z Z, Liu H X, Wu B, et al. Enumeration of spanning trees in a pseudofractal scale-free web[J]. Europhysics Letters, 2010, 90: 68002.

Counting the spanning trees for a class of self-similar planar graphs based on techniques from electrical networks

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 8

Recommended Articles

Metrics

Comments

[1]	Binwu ZHANG, Xiucui GUAN. The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm [J]. Operations Research Transactions, 2022, 26(3): 44-56.
[2]	Yuyang ZHOU, Huizhen ZHANG, Liang MA. An improved immune algorithm for solving hierarchical and progressive location problem of emergency medical facilities [J]. Operations Research Transactions, 2021, 25(2): 15-34.
[3]	LIN Hao, LIN Lan. Optimality characterization of the minimum stretch spanning tree problem for interval graphs [J]. Operations Research Transactions, 2020, 24(4): 153-158.
[4]	WEI Qian, WANG Yongmao. Pricing of power european options based on Tsallis entropy under stochastic interest rate [J]. Operations Research Transactions, 2019, 23(4): 124-130.
[5]	ZHOU Xinyi, WANG Ke, WU Donghua, WANG Chen. Cross entropy algorithm with multiple important sample level estimation for global optimization problems [J]. Operations Research Transactions, 2019, 23(1): 15-27.
[6]	LOU Ye, GAO Yuetian. Some results of convex programming complexity [J]. Operations Research Transactions, 2012, 16(4): 112-124.
[7]	Lou-Ye, SUN Sheng, WU Ming-Nan. A new level-value estimation method for global minimization [J]. Operations Research Transactions, 2012, 16(2): 105-114.
[8]	LI Ying-Hua, LI Xing-Si. The Smooth Tree Option Pricing Model Based On the Minimum Cross Entropy [J]. Operations Research Transactions, 2012, 16(1): 77-87.