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

摘要

For a directed graph G on vertices {0, 1,..., n}, a G-parking function is an n-tuple (b(1),..., b(n)) of non-negative integers such that, for every non-empty subset U subset of {1,..., n}, there exists a vertex j is an element of 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 J(G) of spanning trees of G rooted at 0, thus providing a combinatorial proof of vertical bar P(G)vertical bar = vertical bar J(G)vertical bar. (c) 2004 Elsevier Inc. All rights reserved.