Chip-Firing and the Critical Group of a Graph
N.L. Biggs
DOI: 10.1023/A:1018611014097
Abstract
A variant of the chip-firing game on a graph is defined. It is shown that the set of configurations that are stable and recurrent for this game can be given the structure of an abelian group, and that the order of the group is equal to the tree number of the graph. In certain cases the game can be used to illuminate the structure of the group.
Pages: 25–45
Keywords: chip-firing; discrete Laplacian; tree number; invariant factors
Full Text: PDF
References
1. R. Bacher, P. de la Harpe, and T. Nagnibeda, “The lattice of integral flows and the lattice of integral coboundaries on a finite graph,” Bull. Soc. Math. de France 125 (1997), 167-198.
2. N.L. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge Univ. Press, 1993.
3. N.L. Biggs, “Algebraic potential theory on graphs,” Bull. London Math. Soc. 29 (1997), 641-682.
4. N.L. Biggs, “Chip-firing on distance-regular graphs,” CDAM Research Report Series, LSE-CDAM-96-11, 1996.
5. N.L. Biggs, R.M. Damerell, and D.A. Sands, “Recursive families of graphs,” J. Combinatorial Theory (B) 12 (1972), 123-131.
6. A. Bj\ddot orner and L. Lovász, “Chip-firing games on directed graphs,” J. Alg. Combin. 1 (1992), 305-328.
7. A. Bj\ddot orner, L. Lovász, and P. Shor, “Chip-firing games on graphs,” Europ. J. Comb. 12 (1991), 283-291.
8. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
9. A.E. Brouwer and C.A. van Eijl, “On the p-rank of the adjacency matrices of strongly-regular graphs,” J. Alg. Combin. 1 (1992), 329-346.
10. A. Gabrielov, “Avalanches, sandpiles, and Tutte decomposition,” The Gelfand Mathematical Seminars 1990- 92, Birkhauser, Boston, MA, 1993, pp. 19-26.
11. A. Gabrielov, “Abelian avalanches and Tutte polynomials,” Physica A 195 (1993), 253-274.
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.
2. N.L. Biggs, Algebraic Graph Theory, 2nd edition, Cambridge Univ. Press, 1993.
3. N.L. Biggs, “Algebraic potential theory on graphs,” Bull. London Math. Soc. 29 (1997), 641-682.
4. N.L. Biggs, “Chip-firing on distance-regular graphs,” CDAM Research Report Series, LSE-CDAM-96-11, 1996.
5. N.L. Biggs, R.M. Damerell, and D.A. Sands, “Recursive families of graphs,” J. Combinatorial Theory (B) 12 (1972), 123-131.
6. A. Bj\ddot orner and L. Lovász, “Chip-firing games on directed graphs,” J. Alg. Combin. 1 (1992), 305-328.
7. A. Bj\ddot orner, L. Lovász, and P. Shor, “Chip-firing games on graphs,” Europ. J. Comb. 12 (1991), 283-291.
8. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
9. A.E. Brouwer and C.A. van Eijl, “On the p-rank of the adjacency matrices of strongly-regular graphs,” J. Alg. Combin. 1 (1992), 329-346.
10. A. Gabrielov, “Avalanches, sandpiles, and Tutte decomposition,” The Gelfand Mathematical Seminars 1990- 92, Birkhauser, Boston, MA, 1993, pp. 19-26.
11. A. Gabrielov, “Abelian avalanches and Tutte polynomials,” Physica A 195 (1993), 253-274.
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.