Asymptotic enumeration on self-similar graphs with two boundary vertices
Elmar Teufl, Stephan Wagner
Abstract
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.
Full Text: PDF PostScript