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.)
Keywords:
dual graphs; sandpile group; planar graph
Full Text:
References:
  Bak, P., How nature works:the science of self-organized criticality, (1996), Springer-Verlag Berlin, Heidelberg, New York · Zbl 0894.00007  Bak, P.; Tang, C.; Wiesenfeld, K., Self-organized criticality, Phys. rev. A, 38, 364-374, (1988) · Zbl 1230.37103  Biggs, N., Algebraic graph theory, (1993), Cambridge University Press Cambridge  Biggs, N., Chip-firing and the critical group of a graph, J. algebr. comb., 9, 25-46, (1999) · Zbl 0919.05027  N. Biggs  Björner, A.; Lovász, L.; Shor, P., Chip-firing games on graphs, Europ. J. combinatorics, 12, 283-291, (1991) · Zbl 0729.05048  Dhar, D., Self-organized critical state of sandpile automaton models, Phys. rev. lett., 64, 1613-1616, (1990) · Zbl 0943.82553  Dhar, D.; Majumdar, S.N., Equivalence of the sandpile model and the q← 0 limit of the Potts model, Physica A, 185, 129, (1992)  Dhar, D.; Ruelle, P.; Sen, S.; Verma, D., Algebraic aspects of abelian sandpile models, J. phys. A, 28, 805-831, (1995) · Zbl 0848.68062  Foata, D.; Riordan, J., Mappings of acyclic and parking functions, Aeq. math., 10, 10-22, (1974) · Zbl 0274.05005  Gabrielov, A., Abelian avalanches and Tutte polynomials, Phys. A, 195, 253-274, (1993)  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  O. Marguin, 1997  R. Stanley, Parking functions and noncrossing partitions, Electron. J. Comb. 4 · Zbl 0883.06001  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  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.