Signed Chip Firing Games and symmetric Sandpile Models on the cycles
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 2, pp. 133-146.

We investigate the Sandpile Model and Chip Firing Game and an extension of these models on cycle graphs. The extended model consists of allowing a negative number of chips at each vertex. We give the characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formula for the number of their fixed points.

DOI : 10.1051/ita/2012023
Classification : 05C57, 91A43, 68R15, 68Rxx
Mots-clés : sandpile model, chip firing game, circular distribution, symmetric sandpile model, signed chip firing game, lattice structure 
@article{ITA_2013__47_2_133_0,
     author = {Cori, Robert and Duong Phan, Thi Ha and Huong Tran, Thi Thu},
     title = {Signed {Chip} {Firing} {Games} and symmetric {Sandpile} {Models} on the cycles},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {133--146},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {2},
     year = {2013},
     doi = {10.1051/ita/2012023},
     mrnumber = {3072314},
     zbl = {1266.05098},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2012023/}
}
TY  - JOUR
AU  - Cori, Robert
AU  - Duong Phan, Thi Ha
AU  - Huong Tran, Thi Thu
TI  - Signed Chip Firing Games and symmetric Sandpile Models on the cycles
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2013
SP  - 133
EP  - 146
VL  - 47
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2012023/
DO  - 10.1051/ita/2012023
LA  - en
ID  - ITA_2013__47_2_133_0
ER  - 
%0 Journal Article
%A Cori, Robert
%A Duong Phan, Thi Ha
%A Huong Tran, Thi Thu
%T Signed Chip Firing Games and symmetric Sandpile Models on the cycles
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2013
%P 133-146
%V 47
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2012023/
%R 10.1051/ita/2012023
%G en
%F ITA_2013__47_2_133_0
Cori, Robert; Duong Phan, Thi Ha; Huong Tran, Thi Thu. Signed Chip Firing Games and symmetric Sandpile Models on the cycles. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 2, pp. 133-146. doi : 10.1051/ita/2012023. http://www.numdam.org/articles/10.1051/ita/2012023/

[1] P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality : An explanation of 1/f noise. Phys. Rev. Lett. 59 (1987) 381-284. | MR | Zbl

[2] A. Björner, L. Lovász and P.W. Shor, Chip-firing games on graphs. Eur. J. Combin. 12 (1991) 283-291. | MR | Zbl

[3] R. Cori and D. Rossin, On the sandpile group of dual graphs. Eur. J. Combin. 21 (2000) 447-459. | MR | Zbl

[4] J. Desel, E. Kindler, T. Vesper and R. Walter, A simplified proof for the self-stabilizing protocol : A game of cards. Inf. Process. Lett. 54 (1995) 327-328. | Zbl

[5] D. Dhar, P. Ruelle, S. Sen and D.-N. Verma, Algebraic aspects of abelian sandpile models. J. Phys. A 28 (1995) 805-831. | MR | Zbl

[6] E. Formenti, B. Masson and T. Pisokas, Advances in symmetric sandpiles. Fundam. Inf. 76 (2007) 91-112. | MR | Zbl

[7] E. Goles and M.A. Kiwi, Games on line graphes and sand piles. Theoret. Comput. Sci. 115 (1993) 321-349. | MR | Zbl

[8] E. Goles, M. Morvan and H.D. Phan, Lattice structure and convergence of a game of cards. Ann. Combin. 6 (2002) 327-335. | MR | Zbl

[9] E. Goles, M. Morvan and H.D. Phan. Sandpiles and order structure of integer partitions. Discrete Appl. Math. 117 (2002) 51-64. | MR | Zbl

[10] E. Goles, M. Morvan and H.D. Phan, The structure of linear chip firing game and related models. Theoret. Comput. Sci. 270 (2002) 827-841. | MR | Zbl

[11] É. Goles and M. Latapy, Clémence Magnien, Michel Morvan and Ha Duong Phan. Sandpile models and lattices : a comprehensive survey. Theoret. Comput. Sci. 322 (2004) 383-407. | MR | Zbl

[12] S.-T. Huang. Leader election in uniform rings. ACM Trans. Program. Lang. Syst. 15 (1993) 563-573.

[13] R. Karmakar and S.S. Manna, Particle hole symmetry in a sandpile model, J. Stat. Mech. 2005 (2005) L01002.

[14] M. Latapy and H.D. Phan, The lattice structure of chip firing games. Physica D 115 (2001) 69-82. | MR | Zbl

[15] H.D. Phan, Two sided sand piles model and unimodal sequences. RAIRO - Theor. Inf. Appl. 42 (2008) 631-646. | EuDML | Numdam | MR | Zbl

Cité par Sources :