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 graphsConference paper

Authors: Elmar Teufl 1; Stephan Wagner 2

  • 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 4320(53)n/2(4540)3n. 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.


Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Section: Proceedings
Published on: January 1, 2006
Imported on: May 10, 2017
Keywords: combinatorial enumeration,spanning trees,finite Sierpiński graphs,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

5 Documents citing this article

Consultation statistics

This page has been seen 395 times.
This article's PDF has been downloaded 447 times.