TY - JOUR
T1 - A family of bijections between G-parking functions and spanning trees
AU - Chebikin, Denis
AU - Pylyavskyy, Pavlo
PY - 2005/4
Y1 - 2005/4
N2 - For a directed graph G on vertices {0, 1,...,n}, a G-parking function is an n-tuple (b1,...,bn) of non-negative integers such that, for every non-empty subset U ⊆ {1,...,n}, there exists a vertex j ∈ U for which there are more than bj edges going from j to G - U. We construct a family of bijective maps between the set PG of G-parking functions and the set TG of spanning trees of G rooted at 0, thus providing a combinatorial proof of PG = TG .
AB - For a directed graph G on vertices {0, 1,...,n}, a G-parking function is an n-tuple (b1,...,bn) of non-negative integers such that, for every non-empty subset U ⊆ {1,...,n}, there exists a vertex j ∈ U for which there are more than bj edges going from j to G - U. We construct a family of bijective maps between the set PG of G-parking functions and the set TG of spanning trees of G rooted at 0, thus providing a combinatorial proof of PG = TG .
KW - Parking functions
KW - Spanning trees
UR - http://www.scopus.com/inward/record.url?scp=15844408624&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=15844408624&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2004.08.007
DO - 10.1016/j.jcta.2004.08.007
M3 - Article
AN - SCOPUS:15844408624
SN - 0097-3165
VL - 110
SP - 31
EP - 41
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 1
ER -