Chip-firing games, potential theory on graphs, and spanning trees. (English) Zbl 1408.05089

Baker, Matthew; Shokrieh, Farbod

J. Comb. Theory, Ser. A 120, No. 1, 164-182 (2013).

Summary: We study the interplay between chip-firing games and potential theory on graphs, characterizing reduced divisors (\(G\)-parking functions) on graphs as the solution to an energy (or potential) minimization problem and providing an algorithm to efficiently compute reduced divisors. Applications include an “efficient bijective” proof of Kirchhoff’s matrix-tree theorem and a new algorithm for finding random spanning trees. The running times of our algorithms are analyzed using potential theory, and we show that the bounds thus obtained generalize and improve upon several previous results in the literature.

MSC:

05C57	Games on graphs (graph-theoretic aspects)
05C80	Random graphs (graph-theoretic aspects)
05C05	Trees
91A43	Games involving graphs
31C99	Generalizations of potential theory

Keywords:

chip-firing; potential theory; energy pairing; reduced divisors; matrix-tree theorem; random spanning trees