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

Denis Chebikin, Pavlo Pylyavskyy

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

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 .

Original languageEnglish (US)
Pages (from-to)31-41
Number of pages11
JournalJournal of Combinatorial Theory. Series A
Volume110
Issue number1
DOIs
StatePublished - Apr 2005

Keywords

  • Parking functions
  • Spanning trees

Fingerprint Dive into the research topics of 'A family of bijections between G-parking functions and spanning trees'. Together they form a unique fingerprint.

Cite this