×

zbMATH — the first resource for mathematics

On the sandpile group of dual graphs. (English) Zbl 0969.05034
E. Goles studied the notion of sandpile group in [Sand piles, combinatorial games and cellular automata. Instabilities and nonequilibrium structures III. Math. Appl., 64, 101-121 (1991)].
Let \(G= (X,E)\) be a (nondirected) finite connected graph without loops. The elements of \({\mathcal Z}^n\) (i.e., the vectors of length \(n\) whose components are integers) form an abelian group. By the sandpile group \(\text{SP}(G)\) of \(G\), a factor group of \({\mathcal Z}^n\) is meant (where \(n=|X|\)) with respect to a subgroup defined by means of the adjacency matrix of \(G\).
It is shown that \(\text{SP}(G)\) and \(\text{SP}(G^*)\) are isomorphic if \(G\) is a planar graph and \(G^*\) is its dual, and that to every finite abelian group \({\mathfrak G}\) there is a planar graph \(G\) such that \(\text{SP}(G)\) is isomorphic to \({\mathfrak G}\). The sandpile groups \(\text{SP}(K_n)\) are explicitly determined (\(K_n\) is the complete graph on \(n\) vertices).
Let \(v\) be a cut vertex of \(G\). Denote by \(G_i\) the subgraph induced by \(X_i\cup \{v\}\) where \(X_i\) is one of the vertex classes (split by \(v\)). It is stated that \(\text{SP}(G)\) is the direct product of all the groups \(\text{SP}(G_i)\).
The authors consider models formerly also discussed by D. Dhar [Phys. Rev. Lett. 64, No. 14, 1613-1616 (1990)].

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bak, P., How nature works:the science of self-organized criticality, (1996), Springer-Verlag Berlin, Heidelberg, New York · Zbl 0894.00007
[2] Bak, P.; Tang, C.; Wiesenfeld, K., Self-organized criticality, Phys. rev. A, 38, 364-374, (1988) · Zbl 1230.37103
[3] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press Cambridge
[4] Biggs, N., Chip-firing and the critical group of a graph, J. algebr. comb., 9, 25-46, (1999) · Zbl 0919.05027
[5] N. Biggs
[6] Björner, A.; Lovász, L.; Shor, P., Chip-firing games on graphs, Europ. J. combinatorics, 12, 283-291, (1991) · Zbl 0729.05048
[7] Dhar, D., Self-organized critical state of sandpile automaton models, Phys. rev. lett., 64, 1613-1616, (1990) · Zbl 0943.82553
[8] Dhar, D.; Majumdar, S.N., Equivalence of the sandpile model and the q← 0 limit of the Potts model, Physica A, 185, 129, (1992)
[9] Dhar, D.; Ruelle, P.; Sen, S.; Verma, D., Algebraic aspects of abelian sandpile models, J. phys. A, 28, 805-831, (1995) · Zbl 0848.68062
[10] Foata, D.; Riordan, J., Mappings of acyclic and parking functions, Aeq. math., 10, 10-22, (1974) · Zbl 0274.05005
[11] Gabrielov, A., Abelian avalanches and Tutte polynomials, Phys. A, 195, 253-274, (1993)
[12] Goles, E., sand piles, combinatorial games and cellular automata, instabilities and nonequilibrium structures, III (valparaı́so, 1989), (1991), Kluwer Academic Publishers Dordrecht, p. 101-121
[13] O. Marguin, 1997
[14] R. Stanley, Parking functions and noncrossing partitions, Electron. J. Comb. 4 · Zbl 0883.06001
[15] Stanley, R., hyperplane arrangements, parking functions and tree inversions, mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996), (1998), Birkhäuser Boston, p. 359-375
[16] Tutte, W.T., Graph theory, encyclopedia of mathematics and its applications, 21 ,with a foreword by C. st. J. A. Nash-Williams, (1984), Addison-Wesley Publishing Co Reading, MA · Zbl 0554.05001
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.