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

**AMS Subject Classification: **05C30, 05C05
**Keywords: **parking
functions, critical configurations, spanning forests

dkostic@math.tamu.edu

Annals of Combinatorics 13 (1) pp.103-114 March, 2009

Abstract:

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.
References:

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.