Elmar Teufl ; Stephan Wagner - Asymptotic enumeration on self-similar graphs with two boundary vertices

dmtcs:471 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, Vol. 11 no. 1 - https://doi.org/10.46298/dmtcs.471
Asymptotic enumeration on self-similar graphs with two boundary verticesArticle

Authors: Elmar Teufl 1; Stephan Wagner 2

  • 1 Fakultät für Mathematik = Faculty of Mathematics [Bielefeld]
  • 2 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]

We study two graph parameters, namely the number of spanning forests and the number of connected subgraphs, for self-similar graphs with exactly two boundary vertices. In both cases, we determine the general behavior for these and related auxiliary quantities by means of polynomial recurrences and a careful asymptotic analysis. It turns out that the so-called resistance scaling factor of a graph plays an essential role in both instances, a phenomenon that was previously observed for the number of spanning trees. Several explicit examples show that our findings are likely to hold in an even more general setting.


Volume: Vol. 11 no. 1
Section: Combinatorics
Published on: January 1, 2009
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 511 times.
This article's PDF has been downloaded 317 times.