CoEulerian graphs

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 “<italic>a characterization of those digraphs and initial chip configurations that guarantee finite termination.</italic>” 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sans-serif NP"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="sans-serif">NP</mml:mtext> </mml:mrow> <mml:annotation encoding="application/x-tex">\textsf {NP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-complete for general directed multigraphs.