Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515483 | Journal of Combinatorial Theory, Series A | 2005 | 11 Pages |
Abstract
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|.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Denis Chebikin, Pavlo Pylyavskyy,