The University of Montana
Department of Mathematical Sciences

Technical report #8/2012

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

P. Mark Kayll
Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
mark.kayll@umontana.edu

Dave Perkins
Department of Mathematics
Luzerne County Community College
Nanticoke PA 18634, USA
dperkins@luzerne.edu

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.

Keywords: chip-firing, burn-off games, relaxed legal configurations, Cayley's Formula

AMS Subject Classification: Primary 05C57; Secondary 90D42, 05C30, 05A19, 05C85, 68R10

Download Technical Report: Pdf (309 KB)