# 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.
Keywords :
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.411-414, 2006, DMTCS Proceedings
Domaine :

Littérature citée [4 références]

https://hal.inria.fr/hal-01184698
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 14:24:02
Dernière modification le : jeudi 11 mai 2017 - 01:02:51
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:07:56

### Fichier

dmAG0135.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184698, version 1

### Citation

Elmar Teufl, Stephan Wagner. Spanning trees of finite Sierpiński graphs. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.411-414, 2006, DMTCS Proceedings. 〈hal-01184698〉

### Métriques

Consultations de la notice

## 126

Téléchargements de fichiers