Peter Mark Kayll ; Dave Perkins - A chip-firing variation and a new proof of Cayley's formula

dmtcs:624 - Discrete Mathematics & Theoretical Computer Science, March 18, 2013, Vol. 15 no. 1 -
A chip-firing variation and a new proof of Cayley's formulaArticle

Authors: Peter Mark Kayll 1; Dave Perkins 2

  • 1 Department of Mathematical Sciences [Missoula]
  • 2 Department of Mathematics [Nanticoke]

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.

Volume: Vol. 15 no. 1
Section: Graph Theory
Published on: March 18, 2013
Accepted on: June 9, 2015
Submitted on: July 13, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 798 times.
This article's PDF has been downloaded 429 times.