A family of bijections between G-parking functions and spanning trees

2003/07/22 by Denis Chebikin, Chebikin, Denis, Pavlo Pylyavskyy +1
Mathematics · #05A99 #05C05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A99 #msc:05C05

paper · pdf · doi:10.48550/arxiv.math/0307292

11 pages, 4 figures; a family of bijections containing the two original bijections is presented; submitted to J. Combinatorial Theory, Series A

arxiv created 2004/06/30 · arxiv updated 2009/12/01

Abstract

For a directed graph G on vertices 0,1,...,n, a G-parking function is an n-tuple (b₁,...,b_n) of non-negative integers such that, for every non-empty subset U of 1,...,n, there exists a vertex j in U for which there are more than b_j edges going from j to G-U. We construct a family of bijective maps between the set P_G of G-parking functions and the set T_G of spanning trees of G rooted at 0, thus providing a combinatorial proof of |P_G| = |T_G|.

Related

• Bijections Between Multiparking Functions, Dirichlet Configurations, and Descending R-Traversals
• Generalized Bijective Maps between G-Parking Functions, Spanning\n Trees, and the Tutte Polynomial
• (G,m)-multiparking functions
• G-parking functions and tree inversions
• Parking functions and chip-firing on hypergraphs