A chip-firing variation and a new proof of Cayley's formula

Abstract : We introduce a variation of chip-firing games on connected graphs. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. For a graph G=(V,E), a configuration of 'chips' on its nodes is a mapping C:V→ℕ. We study the configurations that can arise in the course of iterating a burn-off game. After characterizing the 'relaxed legal' configurations for general graphs, we enumerate the 'legal' ones for complete graphs Kn. The number of relaxed legal configurations on Kn coincides with the number tn+1 of spanning trees of Kn+1. Since our algorithmic, bijective proof of this fact does not invoke Cayley's Formula for tn, our main results yield secondarily a new proof of this formula.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.121--132
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990611
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:28:59
Dernière modification le : samedi 5 mai 2018 - 20:22:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:30:16

Fichier

2201-7776-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990611, version 1

Collections

Citation

Peter Mark Kayll, Dave Perkins. A chip-firing variation and a new proof of Cayley's formula. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.121--132. 〈hal-00990611〉

Partager

Métriques

Consultations de la notice

203

Téléchargements de fichiers

216