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 <>
Submitted on : Monday, August 17, 2015 - 2:24:02 PM
Last modification on : Tuesday, December 17, 2019 - 9:30:02 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:07:56 PM

File

dmAG0135.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184698, version 1

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. ⟨hal-01184698⟩

Share

Metrics

Record views

269

Files downloads

829