Chip-firing and critical groups of signed graphs

Matthew Cho, Anton Dochtermann, Ryota Inagaki, Suho Oh, Dylan Snustad, Bailee Zacovic

Published 2023-06-15Version 1

A \textit{signed graph} $G_\phi$ consists of a graph $G$ along with a function $\phi$ that assigns a positive or negative weight to each edge. The reduced signed Laplacian matrix $L_{G_\phi}$ gives rise to a natural notion of chip-firing on $G_\phi$, as well as a critical group ${\mathcal K}(G_\phi)$. Here a negative edge designates an adversarial relationship, so that firing a vertex incident to such an edge leads to a loss of chips at both endpoints. We study chip-firing on signed graphs, employing the theory of chip-firing on invertible matrices introduced by Guzm\'an and Klivans. %Here valid chip configurations are given by the lattice points of a certain cone determined by $G_\phi$ and the underlying graph $G$. This gives rise to notions of \textit{critical} as well as \textit{$z$-superstable} configurations, both of which are counted by the determinant of $L_{G_\phi}$. We establish general results regarding these configurations, focusing on efficient methods of verifying the underlying properties. We then study the critical group of signed graphs in the context of vertex switching and Smith normal forms. We use this to compute the critical groups for various classes of signed graphs including signed cycles, wheels, complete graphs, and fans. In the process we generalize a number of results from the literature.