<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 1" %>
Bijections Between Multiparking Functions, Dirichlet Configurations, and Descending R-Traversals
Dimitrije N. Kosti\'{c}
Department of Mathematics, Texas A&M University, College Station, TX 77843, USA
Annals of Combinatorics 13 (1) pp.103-114 March, 2009
AMS Subject Classification: 05C30, 05C05
There are several combinatorial objects that are known to be in bijection with the spanning trees of a graph $G$. These objects include $G$-parking functions, critical configurations of $G$, and descending traversals of $G$. In this paper, we extend the bijections to generalizations of all three objects.
Keywords: parking functions, critical configurations, spanning forests


1. N. Biggs, Chip Firing and the Critical Group of a Graph, CDAM Research Report Series, 1996; online at: http://www.cdam.lse.ac.uk/Reports/reports96.html.

2. N. Biggs, The Tutte polynomial as a growth function, J. Algebraic Combin. 10 (2) (1999) 115-–133.

3. D. Chebikin and P. Pylyavskyy, A family of bijections between G-parking functions and spanning trees, J. Combin. Theory Ser. A 110 (1) (2005) 31–-41.

4. F. Chung and R.B. Ellis, A chip-ring game and Dirichlet eigenvalues, Discrete Math. 257 (2-3) (2002) 341-–355.

5. R. Cori and Y. Le Borgne, The sand-pile model and Tutte polynomials, Adv. Appl. Math. 30 (1-2) (2003) 44-–52.

6. R. Cori and D. Rossin, On the sandpile group of dual graphs, European. J. Combin. 21 (4) (2000) 447-–459.

7. D. Dhar, Self-organized critical state of the sandpile automaton models, Phys. Rev. Lett. 64 (14) (1990) 1613-–1616.

8. D. Dhar, P. Ruelle, S. Sen, and D-N Verma, Algebraic aspects of abelian sandpile models, J. Phys. A 28 (4) (1995) 805-–831.

9. D. Foata and J. Riordan, Mappings of acyclic and parking functions, Aequationes Math. 10 (1974) 10-–22.

10. A.G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM J. Appl. Math. 14 (6) (1966) 1266-–1274.

11. D. Kosti´c and C. Yan, Multiparking functions, graph searches, and the Tutte polynomial, Adv. Appl. Math. 40 (1) (2008) 73-–97.

12. A. Postnikov and B. Shapiro, Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc. 356 (8) (2004) 3109-–3142.

13. R.P. Stanley, Hyperplane arrangements, parking functions, and tree inversions, In: Mathematical Essays in Honor of Gian-Carlo Rota, B. Sagan and R. Stanley, Eds., Birkh¨auser, Boston, (1988) pp. 359-–375.

14. R.P. Stanley and J. Pittman, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27 (4) (2002) 603–- 634.

15. C.H. Yan, Generalized parking functions, tree inversions, and multicolored graphs, Adv. Appl. Math. 27 (2-3) (2001) 641-–670.