Revista Integración, temas de matemáticas.
Vol. 24 No. 2 (2006): Revista Integración, temas de matemáticas
Research and Innovation Articles

Pilas de arena sobre grafos dirigidos y algo de complejidad

Carolina Mejía Moreno
Escuela de Matemáticas, Universidad Industrial de Santander, Bucaramanga, Colombia.
Bio

Published 2006-10-24

Keywords

  • pilas de arena,
  • laplacianos de grafos,
  • autómatas celulares,
  • complejidad

How to Cite

Mejía Moreno, C. (2006). Pilas de arena sobre grafos dirigidos y algo de complejidad. Revista Integración, Temas De matemáticas, 24(2), 101–116. Retrieved from https://revistas.uis.edu.co/index.php/revistaintegracion/article/view/258

Abstract

In this work we study the Abelian Sandpile Model on directed graphs. The model is more complex on directed graphs than on undirected graphs, because of which there are many questions that remain without an answer. We survey the basic theory of the model on directed graphs and present some new results.

Downloads

Download data is not yet available.

References

[1] L. Babai. The Abelian Sandpile Model. Manuscrito, disponible en http://people.cs.uchicago.edu/~laci/REU05/.

[2] N. Biggs. “Chip-firing and the critical group of a graph”. J. Algebraic Combinatory. 9(1):25-45, 1999.

[3] A. Bjorner & L. Lovasz. “Chip firing games on directed graphs”. European J. Combinatorics. 12(4):305-328, 1992.

[4] F. Chung & R. Ellis. “A chip-firing game and Dirichlet eigenvalues”. Discrete Mathematics, 257:341-355, 2002.

[5] D. Dhar. “Self Organized Critical State of the Sandpile Automaton Model”. Physical Review Letters, 64(14): 1613-1616, 1990.

[6] K. Eriksson. “No polynomial bound for the Chip firing game on directed graphs”. Proceedings American Mathematical Society, 112:1203-1205, 1991.

[7] N. Jacobson. Basic Algebra. W.H. Freeman, San Francisco, 1971.

[8] C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[9] G. Tardos. “Polynomial bound for a chip firing game on graphs”. SIAM J. Discrete Mathematics, 1:397-398, 1988.

[10] E. Toumpakari. On the abelian sandpile model. Ph.D. thesis, Universidad de Chicago, 2005.

[11] L.G. Valiant & V. Vazirani. “NP is as easy as detecting unique solutions”. Theoretical computer Science, 47:85-93, 1986.