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

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (4): 119-126.doi: 10.15960/j.cnki.issn.1007-6093.2022.04.010

• • 上一篇

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

赵伟良^*, 齐林明

浙江工业职业技术学院, 浙江绍兴 312000

收稿日期:2019-11-27 发布日期:2022-11-28
通讯作者: 赵伟良 E-mail:zwlzjipc@163.com
基金资助:
浙江省教育厅2018年度高校访问学者"教师专业发展项目" (No. FX2018113)

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

ZHAO Weiliang^*, QI Linming

Zhejiang Industry Polytechnic College, Shaoxing 312000, Zhejiang, China

Received:2019-11-27 Published:2022-11-28

摘要/Abstract

摘要： Sierpiński多面体是Sierpiński三角形的三维近似, Sierpiński金字塔自相似图是Sierpiński四面体的1-骨架。本文受Sierpiński金字塔图的构造启发, 研究一类构造上极为相似的平面自相似图。基于图的自相似性特点和电网络理论技巧, 得到这类自相似图的生成树的计数公式及生成树增长的熵值。

关键词: Sierpiński三角形, 生成树, 自相似, 电网络等价, 熵值

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

中图分类号:

O157.5

赵伟良, 齐林明. 基于电网络技巧计数一类平面自相似图的生成树数目[J]. 运筹学学报, 2022, 26(4): 119-126.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王蝶, 康丽英. 一般超图的张量谱性质[J]. 运筹学学报, 2023, 27(1): 138-148.
[2]	崔福祥, 杨超, 叶宏波, 姚兵. 图的邻点全和可区别全染色[J]. 运筹学学报, 2023, 27(1): 149-158.
[3]	李春梅, 王治文. Δ(G)=5的2-连通外平面图的邻点可区别全染色[J]. 运筹学学报, 2021, 25(4): 120-126.
[4]	董艳侠, 薛涛, 张广. 广义de Bruijn有向图的k-元控制集[J]. 运筹学学报, 2021, 25(2): 127-134.
[5]	刘瑶. 带松弛条件的图的强边着色[J]. 运筹学学报, 2021, 25(2): 115-126.
[6]	林晓霞. 关于拟k-连通图的一个注释[J]. 运筹学学报, 2021, 25(1): 137-140.
[7]	陈敏, 杨建民, 张豪, 王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136.
[8]	赵静, 单而芳, 赵加贵. 最大边连通和super-边连通超图的充分条件[J]. 运筹学学报, 2021, 25(1): 123-131.
[9]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[10]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[11]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[12]	裴建峰, 林上为. 极大限制边连通超图的两个充分条件[J]. 运筹学学报, 2019, 23(2): 120-126.
[13]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[14]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[15]	陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.