Parallel chip-firing games on directed graphsIn 1992, Bitar and Goles introduced the parallel chip-firing game on undirected graphs. Two years later, Prisner extended the game to directed graphs. While the properties of parallel chip-firing games on undirected graphs have been extensively studied, their analogs for parallel chip-firing games on directed graphs have been sporadic. In this paper, we prove the outstanding analogs of the core results of parallel chip-firing games on undirected graphs for those on directed graphs. We find the possible periods of a parallel chip-firing game on a directed simple cycle and use Gauss-Jordan Elimination on a Laplacian-like matrix to establish a lower bound on the maximum period of a parallel chip-firing game on a directed complete graph and a directed complete bipartite graph. Finally, we use the method of motors by Jiang, Scully, and Zhang to show that a binary string $s$ can be the atomic firing sequence of a vertex in a parallel chip-firing game on a strongly connected directed graph if and only if $s$ contains 1 or $s=0$.
arxiv.org