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

P. Mark Kayll; Dave Perkins

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

P. Mark Kayll, Dave Perkins

Mathematics

Luzerne County Community College

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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 K_n+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.

Original language	English
Pages (from-to)	121-132
Number of pages	12
Journal	Discrete Mathematics and Theoretical Computer Science
Volume	15
Issue number	1
State	Published - 2013

Keywords

Burn-off games
Cayley's Formula
Chip-firing
Relaxed legal configurations

Cite this

@article{a4f72ab111bb437bb408f62209eb991a,

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 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 = "Burn-off games, Cayley's Formula, Chip-firing, Relaxed legal configurations",

author = "Kayll, {P. Mark} and Dave Perkins",

year = "2013",

language = "English",

volume = "15",

pages = "121--132",

journal = "Discrete Mathematics and Theoretical Computer Science",

issn = "1462-7264",

publisher = "Maison de l'informatique et des mathematiques discretes",

number = "1",

}

TY - JOUR

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

AU - Kayll, P. Mark

AU - Perkins, Dave

PY - 2013

Y1 - 2013

N2 - 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 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.

AB - 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 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.

KW - Burn-off games

KW - Cayley's Formula

KW - Chip-firing

KW - Relaxed legal configurations

UR - http://www.scopus.com/inward/record.url?scp=84876908964&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84876908964

SN - 1462-7264

VL - 15

SP - 121

EP - 132

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

IS - 1

ER -

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

Abstract

Keywords

Other files and links

Fingerprint

Cite this