Asymptotic enumeration on self-similar graphs with two boundary vertices - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2009

Asymptotic enumeration on self-similar graphs with two boundary vertices

Résumé

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.
Fichier principal
Vignette du fichier
969-4053-1-PB.pdf (203.21 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00988183 , version 1 (07-05-2014)

Identifiants

Citer

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

Collections

TDS-MACS
85 Consultations
839 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More