Chip-firing and the critical group of a graph
type: Item
instance of: scholarly article
title: Chip-firing and the critical group of a graph
zbMATH Open document ID: 0919.05027
DOI: 10.1023/A:1018611014097
published in: Journal of Algebraic Combinatorics
publication date: 1999-08-23T00:00:00Z
review text: 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\).
reviewed by: Brigitte Servatius
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1275779
zbMATH Keywords: chip firing
zbMATH Keywords: critical group
zbMATH Keywords: avalanche
zbMATH Keywords: discrete Laplacian
zbMATH Keywords: tree number
zbMATH Keywords: invariant factor
author: Norman L. Biggs
MaRDI profile type: Publication
cites work: The lattice of integral flows and the lattice of integral cuts on a finite graph
cites work: Algebraic Graph Theory
cites work: Algebraic Potential Theory on Graphs
cites work: Recursive families of graphs
cites work: Chip-firing games on directed graphs
cites work: Chip-firing games on graphs
cites work: Q3992965
cites work: On the \(p\)-rank of the adjacency matrices of strongly regular graphs
cites work: Q4279783
cites work: Q4841309
description: scientific article; zbMATH DE number 1275779