Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

   
 
 

 

CoEulerian graphs


Authors: Matthew Farrell and Lionel Levine
Journal: Proc. Amer. Math. Soc. 144 (2016), 2847-2860
MSC (2010): Primary 05C05, 05C20, 05C45, 05C50, 68Q25
DOI: https://doi.org/10.1090/proc/12952
Published electronically: December 21, 2015
MathSciNet review: 3487219
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We suggest a measure of ``Eulerianness'' of a finite directed graph and define a class of ``coEulerian'' graphs. These are the graphs whose Laplacian lattice is as large as possible. As an application, we address a question in chip-firing posed by Björner, Lovász, and Shor in 1991, who asked for ``a characterization of those digraphs and initial chip configurations that guarantee finite termination.'' Björner and Lovász gave an exponential time algorithm in 1992. We show that this can be improved to linear time if the graph is coEulerian, and that the problem is $ \textsf {NP}$-complete for general directed multigraphs.


References [Enhancements On Off] (What's this?)

  • [1] David J. Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math. 3 (1990), no. 4, 450-465. MR 1069105 (91h:60013), https://doi.org/10.1137/0403039
  • [2] Omid Amini and Madhusudan Manjunath, Riemann-Roch for sub-lattices of the root lattice $ A_n$, Electron. J. Combin. 17 (2010), no. 1, Research Paper 124, 50. MR 2729373 (2012a:06009)
  • [3] Arash Asadi and Spencer Backman, Chip-firing and Riemann-Roch theory for directed graphs, Electronic Notes Discrete Math. 38 (2011), 63-68. arXiv:1012.0287
  • [4] Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766-788. MR 2355607 (2008m:05167), https://doi.org/10.1016/j.aim.2007.04.012
  • [5] Anders Björner and László Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992), no. 4, 305-328. MR 1203679 (94c:90132), https://doi.org/10.1023/A:1022467132614
  • [6] Anders Björner, László Lovász, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283-291. MR 1120415 (92g:90193), https://doi.org/10.1016/S0195-6698(13)80111-4
  • [7] Benjamin Bond and Lionel Levine, Abelian networks I. Foundations and examples, 2013. arXiv:1309.3445
  • [8] Benjamin Bond and Lionel Leivne, Abelian networks II. Halting on all inputs, Selecta Math., to appear, 2015. arXiv:1409.0169
  • [9] Andrei Broder, Generating random spanning trees. In Symp. Foundations of Computer Sci., IEEE, New York, 442-447, 1989.
  • [10] Swee Hong Chan, Abelian sandpile model and Biggs-Merino polynomial for directed graphs, 2014. arXiv:1412.4837
  • [11] Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613-1616. MR 1044086 (90m:82053), https://doi.org/10.1103/PhysRevLett.64.1613
  • [12] P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50-59. MR 882842 (88e:65047), https://doi.org/10.1287/moor.12.1.50
  • [13] Kimmo Eriksson, No polynomial bound for the chip firing game on directed graphs, Proc. Amer. Math. Soc. 112 (1991), no. 4, 1203-1205. MR 1065944 (91j:90110), https://doi.org/10.2307/2048674
  • [14] M. A. Frumkin, Polynomial time algorithms in the theory of linear Diophantine equations, Fundamentals of computation theory (Proc. Internat. Conf., Poznań-Kórnik, 1977) Lecture Notes in Comput. Sci., Vol. 56. Springer, Berlin, 1977, pp. 386-392. MR 0502229 (58 #19343)
  • [15] James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068-1083. MR 1135749 (93d:15021), https://doi.org/10.1137/0220067
  • [16] C. Hermite, Sur l'introduction des variables continues dans la théorie des nombres, J. Reine Angew. Math. 41 (1851), 191-216 (French). MR 1578717, https://doi.org/10.1515/crll.1851.41.191
  • [17] Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331-364. MR 2477390 (2010f:82066), https://doi.org/10.1007/978-3-7643-8786-0_17
  • [18] Viktor Kiss and Lilla Tóthmérész, Chip-firing games on Eulerian digraphs and $ \mathbf {NP}$-hardness of computing the rank of a divisor on a graph, Discrete Appl. Math. 193 (2015), 48-56. MR 3371611, https://doi.org/10.1016/j.dam.2015.04.030
  • [19] Lionel Levine, Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle, Comm. Math. Phys. 335 (2015), no. 2, 1003-1017. MR 3316648, https://doi.org/10.1007/s00220-014-2216-5
  • [20] David Perkinson, Jacob Perlman, and John Wilmes, Primer for the algebraic geometry of sandpiles, Tropical and non-Archimedean geometry, Contemp. Math., vol. 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211-256. MR 3204273, https://doi.org/10.1090/conm/605/12117
  • [21] Kévin Perrot and Trung Van Pham, Chip-firing and partial Tutte polynomial for Eulerian digraphs, 2013. arXiv:1306.0294
  • [22] Trung Van Pham, Orbits of rotor-router operation and stationary distribution of random walks on directed graphs, Adv. in Appl. Math. 70 (2015), 45-53. MR 3388864, https://doi.org/10.1016/j.aam.2015.06.006
  • [23] Günter Schaar, Remarks on Hamiltonian properties of powers of digraphs, Discrete Appl. Math. 51 (1994), no. 1-2, 181-186. 2nd Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1991). MR 1279633 (95a:05047), https://doi.org/10.1016/0166-218X(94)90107-4
  • [24] Eugene R. Speer, Asymmetric abelian sandpile models, J. Statist. Phys. 71 (1993), no. 1-2, 61-74. MR 1215850 (94f:82051), https://doi.org/10.1007/BF01048088
  • [25] Richard P. Stanley, Enumerative combinatorics. Vol. 2. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. MR 1676282 (2000k:05026)
  • [26] Gábor Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math. 1 (1988), no. 3, 397-398. MR 955655 (89i:68103), https://doi.org/10.1137/0401039
  • [27] David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) ACM, New York, 1996, pp. 296-303. MR 1427525, https://doi.org/10.1145/237814.237880
  • [28] Bohdan Zelinka, Centers of directed cacti, Časopis Pěst. Mat. 114 (1989), no. 3, 225-229 (English, with Russian and Czech summaries). MR 1016631 (90i:05043)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C05, 05C20, 05C45, 05C50, 68Q25

Retrieve articles in all journals with MSC (2010): 05C05, 05C20, 05C45, 05C50, 68Q25


Additional Information

Matthew Farrell
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14850
Email: msf235@cornell.edu

Lionel Levine
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14850

DOI: https://doi.org/10.1090/proc/12952
Keywords: Chip-firing, critical group, Eulerian digraph, Laplacian lattice, oriented spanning tree, period vector, Pham index, sandpile group
Received by editor(s): May 26, 2015
Received by editor(s) in revised form: September 2, 2015, and September 4, 2015
Published electronically: December 21, 2015
Additional Notes: This research was supported by NSF grants DMS-1243606 and DMS-1455272 and a Sloan Fellowship.
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2015 by the authors

American Mathematical Society