Skip to Main content Skip to Navigation
Journal articles

Asymptotic enumeration on self-similar graphs with two boundary vertices

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-00988183
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, May 7, 2014 - 3:36:45 PM
Last modification on : Tuesday, December 17, 2019 - 9:30:02 AM
Long-term archiving on: : Thursday, August 7, 2014 - 11:36:46 AM

File

969-4053-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00988183, version 1

Collections

Citation

Elmar Teufl, Stephan Wagner. Asymptotic enumeration on self-similar graphs with two boundary vertices. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.11--31. ⟨hal-00988183⟩

Share

Metrics

Record views

401

Files downloads

876