$G$-Parking Functions, Acyclic Orientations and Spanning Trees
Authors:
- Brian BensonBBBrian Benson
- Deeparnab ChakrabartyDCDeeparnab Chakrabarty
- Prasad TetaliPTPrasad Tetali
Preprint
Abstract
Given an undirected graph $G=(V,E)$, and a designated vertex $q\in V$, the notion of a $G$-parking function (with respect to $q$) was independently developed and studied by various authors, and has recently gained renewed attention. This notion generalizes the classical notion of a parking function associated with the complete graph. In this work, we study properties of {\em maximum} $G$-parking functions and provide a new bijection between them and the set of spanning trees of $G$ with no broken circuit. As a case study, we specialize some of our results to the graph corresponding to the discrete $n$-cube $Q_n$. We present the article in an expository self-contained form, since we found the combinatorial aspects of $G$-parking functions somewhat scattered in the literature, typically treated in conjunction with sandpile models and closely related chip-firing games.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Activity preserving bijections between spanning trees and orientations in graphsDiscrete Mathematics, 2005
- A family of bijections between -parking functions and spanning treesJournal of Combinatorial Theory, Series A, 2005
- The sand-pile model and Tutte polynomialsAdvances in Applied Mathematics, 2003
- Algebraic Graph Theory2001
- Sinks in Acyclic Orientations of GraphsJournal of Combinatorial Theory, Series B, 2000
- On the Sandpile Group of Dual GraphsEuropean Journal of Combinatorics, 2000
- Chip firing and the tutte polynomialAnnals of Combinatorics, 1997
- Abelian avalanches and Tutte polynomialsPhysica A: Statistical Mechanics and its Applications, 1993
- Chip-firing Games on GraphsEuropean Journal of Combinatorics, 1991
- Bijective proofs of two broken circuit theoremsJournal of Graph Theory, 1986