Chip-firing and the critical group of a graph (Q1283502): Difference between revisions

Let \(G\) be a graph with perhaps multiple edges in which each vertex \(v\) is labeled with an integer \(s(v)\). A firing of a vertex is a modification of the vertex labeling increasing the label of each neighbor \(w\) of \(v\) by one for each edge between \(v\) and \(w\), and decreasing the label on \(v\) by the degree of \(v\) (essentially distributing a chip to each neighbor). Chip firing in graphs has been studied in \textit{A. Björner} and \textit{L. Lovász} [J. Algebr. Comb. 1, No. 4, 305-328 (1992; Zbl 0805.90142)] and with different terminology in \textit{A. Gabrielov} [Avalanches, sandpiles and Tutte decomposition, in: L. Corwin et al. (ed.), The Gelfand Seminars, 1990-1992, 19-26 (1993; Zbl 0786.60124)]. In this paper the author considers a variant of the game in which all vertex labels are positive except for one distinguished vertex whose label is always negative (the government). The main result is that the critical labelings can be given the structure of an abelian group whose order is the number of spanning trees of \(G\).