Parallel Chip Firing on Digraphs
Erich Prisner
Mathematisches Seminar, Universität Hamburg,
Bundesstraße 55, 20146 Hamburg, Germany
Abstract
Given some multidigraph, a state is any distribution of some chips on its vertices. We transform this initial state step by step. Every vertex checks whether it is able to send one chip through every outgoing arc. If it can, it does; otherwise it does not send any chip. All vertices check and send in parallel. Finally, at every vertex all incoming chips are added to the remaining chips. This transformation on the set of states is iterated.
If the digraph and the total number of chips are finite, then we finally arrive at some periodic configuration. Here we investigate how these periodic configurations depend on the digraph and the total number of chips. There is a sharp contrast in the behavior for Eulerian digraphs (where the in-degree of each vertex equals its out-degree) and non-Eulerian digraphs.