Discrete Mathematics & Theoretical Computer Science, Vol 15, No 1 (2013)

Font Size:  Small  Medium  Large

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

Peter Mark Kayll, Dave Perkins

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.

Full Text: PDF PostScript