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.
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
.
DOI: 10.15960/j.cnki.issn.1007-6093.2022.04.010
[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.
