The Number of Spanning Trees in Self-Similar Graphs |
| |
Authors: | Elmar Teufl Stephan Wagner |
| |
Institution: | 1. Fachbereich Mathematik, Eberhard Karls Universit?t T??bingen, Auf der Morgenstelle 10, 72076, T??bingen, Germany 2. Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland, 7602, South Africa
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|