DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

Spanning trees of finite Sierpiński graphs

Elmar Teufl, Stephan Wagner

Abstract


We show that the number of spanning trees in the finite Sierpiński graph of level n is given by (3 / 20)1/4 (5 / 3)-n/2 ( 540 )3n/4. 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.

Full Text: PDF

Valid XHTML 1.0 Transitional