Parking Functions and Acyclic Orientations of Graphs
Brian Benson, Prasad Tetali · arXiv (Cornell University) · 2008
Given an undirected graph G=(V, E), and a designated vertex q∈V, the notion of a G-parking function (with respect to q) has recently been developed and studied by various authors. This notion generalizes the classical notion of a parking function associated with the complete graph. In this work, we study properties of certain maximum G-parking functions and relate them, in a bijective way, to another classical combinatorial object – the set of acyclic orientations of G. As a case study, we specialize some of our results to the graph corresponding to the discrete n-cube Qn, and provide a combinatorial explanation for a significant factor appearing in the number of spanning trees of Qn.