A chip-firing game and Dirichlet eigenvalues Original Research Article

We consider a variation of the chip-firing game in an induced subgraph S of a graph G. Starting from a given chip configuration, if a vertex v has at least as many chips as its degree, we can fire v by sending one chip along each edge from v to its neighbors. Chips are removed at the boundary δS. The game continues until no vertex can be fired. We will give an upper bound, in terms of Dirichlet eigenvalues, for the number of firings needed before a game terminates. We also examine the relations among three equinumerous families, the set of spanning forests on S with roots in the boundary of S, a set of “critical” configurations of chips, and a coset group, called the sandpile group associated with S.