A chip-firing variation and a new proof of Cayley's formula - 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 : 2013

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

Résumé

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

Dates et versions

hal-00990611 , version 1 (13-05-2014)

Identifiants

Citer

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

Collections

TDS-MACS
64 Consultations
879 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More