<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The Number of Spanning Trees in Self-Similar Graphs
Elmar Teufl1 and Stephan Wagner2
1Fachbereich Mathematik, Eberhard Karls Universit¨at T¨ubingen, Auf der Morgenstelle 10, 72076 T¨ubingen, Germany
2Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa
Annals of Combinatorics 15 (2) pp.355-380 April, 2011
AMS Subject Classification: 05C30; 05C05, 34B45
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´nski 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: spanning trees, self-similar graphs


1. Barlow, M.T.: Diffusions on fractals. In: Bernard, P. (ed.) Lectures on Probability Theory and Statistics, pp. 1–121. Springer, Berlin (1998)

2. Berge, C.: Graphs and Hypergraphs. North-Holland Publishing Co., Amsterdam (1976)

3. Bollobás, B.: Modern Graph Theory. Graduate Texts in Mathematics, Vol. 184. Springer-Verlag, New York (1998)

4. Brown, T.J.N., Mallion, R.B., Pollak, P., Roth, A.: Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes. Discrete Appl. Math. 67(1-3), 51–66 (1996)

5. Cayley, A.: A theorem on trees. Quart. J. Math. 23, 376–378 (1889)

6. Chaiken, S.: A combinatorial proof of the all minors matrix tree theorem. SIAM J. Algebraic Discrete Methods 3(3), 319–329 (1982)

7. Chang, S.-C., Chen, L.-C., Yang, W.-S., Spanning trees on the Sierpinski gasket. J. Stat. Phys. 126(3), 649–667 (2007)

8. Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press, New York (1987)

9. Guido, D., Isola, T., Lapidus, M.L.: A trace on fractal graphs and the Ihara zeta function. Trans. Amer. Math. Soc. 361(6), 3041–3070 (2009)

10. Harary, F., Palmer, E.M.: Graphical Enumeration. Academic Press, New York (1973)

11. Kigami, J.: Analysis on Fractals. Cambridge Tracts in Mathematics, Vol. 143. Cambridge University Press, Cambridge (2001)

12. Kirchhoff, G.R.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme gef¨uhrt wird. Ann. Phys. Chem. 72, 497–508 (1847)

13. Kr¨on, B.: Growth of self-similar graphs. J. Graph Theory 45(3), 224–239 (2004)

14. Lyons, R.: Asymptotic enumeration of spanning trees. Combin. Probab. Comput. 14(4), 491–522 (2005)

15. Metz, V.: The short-cut test. J. Funct. Anal. 220(1), 118–156 (2005)

16. Moon, J.W.: Some determinant expansions and the matrix-tree theorem. Discrete Math. 124(1-3), 163–171 (1994)

17. Neunhäuserer, J.: Random walks on infinite self-similar graphs. Electron. J. Probab. 12(46), 1258–1275 (2007)

18. Sabot, C.: Spectral properties of self-similar lattices and iteration of rational maps. M´em. Soc. Math. Fr. (N.S.) 92, (2003)

19. Shima, T.: On eigenvalue problems for Laplacians on p.c.f. self-similar sets. Japan J. Indust. Appl. Math. 13(1), 1–23 (1996)

20. Shrock, R., Wu, F.Y.: Spanning trees on graphs and lattices in d dimensions. J. Phys. A 33(21), 3881–3902 (2000)

21. Teufl, E.,Wagner, S.: The number of spanning trees of finite Sierpi´nski graphs. In: Fourth Colloquium on Mathematics and Computer Science, pp. 411–414. Nancy (2006)

22. Teufl, E.,Wagner, S.: Enumeration problems for classes of self-similar graphs. J. Combin. Theory Ser. A 114(7), 1254–1277 (2007)