$G$-Parking Functions, Acyclic Orientations and Spanning Trees

Details $G$-Parking Functions, Acyclic Orientations and Spanning Trees $G$-Parking Functions, Acyclic Orientations and Spanning Trees

2008-01-07

arxiv.org/abs/0801.1114v3

B. Benson, D. Chakrabarty, P. Tetali. Discrete Mathematics 310 (2010) 1340-1353

Mathematics

Combinatorics

Added coauthor, extension of v2 with additional results and references. 28 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

$G$-Parking Functions, Acyclic Orientations and Spanning Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with $G$-Parking Functions, Acyclic Orientations and Spanning Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $G$-Parking Functions, Acyclic Orientations and Spanning Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-420340