Paper Info
Title
A chip-firing variation and a new proof of Cayley's Formula.
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 K-n. The number of relaxed legal configurations on K-n coincides with the number t(n+1) of spanning trees of Kn+1. Since our algorithmic, bijective proof of this fact does not invoke Cayley's Formula for t(n), our main results yield secondarily a new proof of this formula.
Year
Venue
Keywords
2013
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
chip-firing,burn-off games,relaxed legal configurations,Cayley's Formula
Field
DocType
Volume
Discrete mathematics,Cayley's formula,Graph,Combinatorics,Chip,Bijective proof,Spanning tree,Mathematics
Journal
15.0
Issue
ISSN
Citations 
1.0
1462-7264
1
PageRank 
References 
Authors
0.48
2
2
Name
Order
Citations
PageRank
P. Mark Kayll1658.34
Dave Perkins210.48