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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.11--31
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00988183
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 7 mai 2014 - 15:36:45
Dernière modification le : mercredi 29 novembre 2017 - 10:26:23
Document(s) archivé(s) le : jeudi 7 août 2014 - 11:36:46

Fichier

969-4053-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

281

Téléchargements de fichiers

156