×

zbMATH — the first resource for mathematics

Chip-firing and the critical group of a graph. (English) Zbl 0919.05027
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 A. Björner and L. Lovász [J. Algebr. Comb. 1, No. 4, 305-328 (1992; Zbl 0805.90142)] and with different terminology in 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\).

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacher, R.; de la Harpe, P.; Nagnibeda, T., The lattice of integral flows and the lattice of integral coboundaries on a finite graph, Bull. Soc. Math. de France, 125, 167-198, (1997) · Zbl 0891.05062
[2] N.L. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge Univ. Press, 1993.
[3] Biggs, N. L., Algebraic potential theory on graphs, Bull. London Math. Soc., 29, 641-682, (1997)
[4] N.L. Biggs, “Chip-firing on distance-regular graphs,” CDAM Research Report Series, LSE-CDAM-96-11, 1996.
[5] Biggs, N. L.; Damerell, R. M.; Sands, D. A., Recursive families of graphs, J. Combinatorial Theory (B), 12, 123-131, (1972) · Zbl 0215.05504
[6] Björner, A.; Lovász, L., Chip-firing games on directed graphs, J. Alg. Combin., 1, 305-328, (1992) · Zbl 0805.90142
[7] Björner, A.; Lovász, L.; Shor, P., Chip-firing games on graphs, Europ. J. Comb., 12, 283-291, (1991) · Zbl 0729.05048
[8] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
[9] Brouwer, A. E.; van Eijl, C. A., On the \(p\)-rank of the adjacency matrices of strongly-regular graphs, J. Alg. Combin., 1, 329-346, (1992) · Zbl 0780.05039
[10] Gabrielov, A., Avalanches, sandpiles, and Tutte decomposition, 19-26, (1993), Boston, MA · Zbl 0786.60124
[11] Gabrielov, A., Abelian avalanches and Tutte polynomials, Physica A, 195, 253-274, (1993)
[12] L. Lovász and P. Winkler, “Mixing of random walks and other diffusions on a graph,” in Surveys in Combinatorics 1995, P. Rowlinson (Ed.), Cambridge University Press, 1995, pp. 119-154. · Zbl 0826.60057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.