Skip to Main content Skip to Navigation
Conference papers

Spanning trees of finite Sierpiński graphs

Abstract : 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.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184698
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 17, 2015 - 2:24:02 PM
Last modification on : Thursday, January 6, 2022 - 12:28:03 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:07:56 PM

File

dmAG0135.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Elmar Teufl, Stephan Wagner. Spanning trees of finite Sierpiński graphs. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.411-414, ⟨10.46298/dmtcs.3494⟩. ⟨hal-01184698⟩

Share

Metrics

Record views

184

Files downloads

480