Integral flow and cycle chip-firing on graphs

Abstract

Motivated by the notion of chip-firing on the dual graph of a planar graph, we consider `integral flow chip-firing' on an arbitrary graph $G$. The chip-firing rule is governed by ${\mathcal{L}}^{\ast }(G)$, the dual Laplacian of $G$ determined by choosing a basis for the lattice of integral flows on $G$. We show that any graph admits such a basis so that ${\mathcal{L}}^{\ast }(G)$ is an $M$-matrix, leading to a firing rule on these basis elements that is avalanche finite. This follows from a more general result on bases of integral lattices that may be of independent interest. Our results provide a notion of $z$-superstable flow configurations that are in bijection with the set of spanning trees of $G$. We show that for planar graphs, as well as for the graphs $K_5$ and $K_{3,3}$, one can find such a flow M-basis that consists of cycles of the underlying graph. We consider the question for arbitrary graphs and address some open questions.

18 pages, 4 figures; v2: typos fixed, other minor changes; v3: title change, author name corrected, some changes in terminology, other corrections and minor revisions incorporating comments from referees

References in corpus (1)

• Chip-firing games, potential theory on graphs, and spanning trees