Elmar Teufl ; Stephan Wagner
-
Spanning trees of finite Sierpiński graphs
dmtcs:3494 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2006,
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
-
https://doi.org/10.46298/dmtcs.3494
Spanning trees of finite Sierpiński graphsArticle
Authors: Elmar Teufl 1; Stephan Wagner 2
NULL##NULL
Elmar Teufl;Stephan Wagner
1 Fakultät für Mathematik = Faculty of Mathematics [Bielefeld]
2 Institut für Mathematik [Graz]
We show that the number of spanning trees in the finite Sierpiński graph of level $n$ is given by $\sqrt[4]{\frac{3}{20}} (\frac{5}{3})^{-n/2} (\sqrt[4]{540})^{3^n}$. The proof proceeds in two steps: First, we show that the number of spanning trees and two further quantities satisfy a $3$-dimensional polynomial recursion using the self-similar structure. Secondly, it turns out, that the dynamical behavior of the recursion is given by a $2$-dimensional polynomial map, whose iterates can be computed explicitly.
Elmar Teufl;Stephan Wagner, 2011, The Number of Spanning Trees in Self-Similar Graphs, Annals of Combinatorics, 15, 2, pp. 355-380, 10.1007/s00026-011-0100-y.
Elmar Teufl;Stephan Wagner, 2009, Asymptotic enumeration on self-similar graphs with two boundary vertices, Discrete Mathematics & Theoretical Computer Science, Vol. 11 no. 1, Combinatorics, 10.46298/dmtcs.471, https://doi.org/10.46298/dmtcs.471.
Elmar Teufl;Stephan Wagner, 2009, Spanning forests, electrical networks, and a determinant identity, Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK,..., Proceedings, 10.46298/dmtcs.2699, https://doi.org/10.46298/dmtcs.2699.
Flaminia L. Luccio, 2008, Contiguous Search Problem in Sierpiński Graphs, Theory of Computing Systems, 44, 2, pp. 186-204, 10.1007/s00224-008-9116-z.
Flaminia L. Luccio, Lecture notes in computer science, Intruder Capture in Sierpiński Graphs, pp. 249-261, 2007, 10.1007/978-3-540-72914-3_22.