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?)


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