The Number of Spanning Trees in Self-Similar Graphs

被引：0
作者：
Elmar Teufl
Stephan Wagner
机构：
[1] Eberhard Karls Universität Tübingen,Fachbereich Mathematik
[2] Stellenbosch University,Department of Mathematical Sciences
来源：
Annals of Combinatorics | 2011年 / 15卷
关键词：
05C30; 05C05; 34B45; spanning trees; self-similar graphs;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The number of spanning trees of a graph, also known as the complexity, is computed for graphs constructed by a replacement procedure yielding a self-similar structure. It is shown that under certain symmetry conditions exact formulas for the complexity can be given. These formulas indicate interesting connections to the theory of electrical networks. Examples include the well-known Sierpiński graphs and their higher-dimensional analogues. Several auxiliary results are provided on the way—for instance, a property of the number of rooted spanning forests is proven for graphs with a high degree of symmetry.
引用
收藏
页码：355 / 380
页数：25
相关论文
共 23 条
  • [1] Brown T.J.N.(1996)Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes Discrete Appl. Math. 67 51-66
  • [2] Mallion R.B.(1889)A theorem on trees Quart. J. Math. 23 376-378
  • [3] Pollak P.(1982)A combinatorial proof of the all minors matrix tree theorem SIAM J. Algebraic Discrete Methods 3 319-329
  • [4] Roth A.(2007)Spanning trees on the Sierpinski gasket J. Stat. Phys. 126 649-667
  • [5] Cayley A.(2009)A trace on fractal graphs and the Ihara zeta function Trans. Amer. Math. Soc. 361 3041-3070
  • [6] Chaiken S.(1847)Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird Ann. Phys. Chem. 72 497-508
  • [7] Chang S.-C.(2004)Growth of self-similar graphs J. Graph Theory 45 224-239
  • [8] Chen L.-C.(2005)Asymptotic enumeration of spanning trees Combin. Probab. Comput. 14 491-522
  • [9] Yang W.-S.(2005)The short-cut test J. Funct. Anal. 220 118-156
  • [10] Guido D.(1994)Some determinant expansions and the matrix-tree theorem Discrete Math. 124 163-171
123