کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648435 | 1342411 | 2010 | 14 صفحه PDF | دانلود رایگان |
Given an undirected graph G=(V,E)G=(V,E), and a designated vertex q∈Vq∈V, the notion of a GG-parking function (with respect to qq) was independently developed and studied by various authors, and has recently gained renewed attention. This notion generalizes the classical notion of a parking function associated with the complete graph. In this work, we study the properties of maximum GG-parking functions and provide a new bijection between them and the set of spanning trees of GG with no broken circuit. As a case study, we specialize some of our results to the graph corresponding to the discrete nn-cube QnQn. We present the article in an expository self-contained form, since we found the combinatorial aspects of GG-parking functions somewhat scattered in the literature, typically treated in conjunction with sandpile models and closely related chip-firing games.
Journal: Discrete Mathematics - Volume 310, Issue 8, 28 April 2010, Pages 1340–1353