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

P. Mark Kayll, Dave Perkins

Research output: Contribution to journalArticlepeer-review

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 → N. 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.

Original languageEnglish
Pages (from-to)121-132
Number of pages12
JournalDiscrete Mathematics and Theoretical Computer Science
Volume15
Issue number1
StatePublished - 2013

Keywords

  • Burn-off games
  • Cayley's Formula
  • Chip-firing
  • Relaxed legal configurations

Fingerprint

Dive into the research topics of 'A chip-firing variation and a new proof of Cayley's Formula'. Together they form a unique fingerprint.

Cite this