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