CoEulerian graphs
From MaRDI portal
Publication:2802106
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 Bjorner, Lovasz, and Shor in 1991, who asked for "a characterization of those digraphs and initial chip configurations that guarantee finite termination." Bjorner and Lovasz 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 NP-complete for general directed multigraphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 3572260 (Why is no real title available?)
- scientific article; zbMATH DE number 1256746 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- Abelian networks. I: Foundations and examples
- Abelian networks. II: Halting on all inputs
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- Asymmetric Abelian sandpile models
- Asymptotically Fast Triangularization of Matrices over Rings
- Centers of directed cacti
- Chip-Firing and Rotor-Routing on Directed Graphs
- Chip-firing and Riemann-Roch theory for directed graphs
- Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
- Chip-firing games on directed graphs
- Chip-firing games on graphs
- Hermite Normal Form Computation Using Modulo Determinant Arithmetic
- No Polynomial Bound for the Chip Firing Game on Directed Graphs
- Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
- Polynomial Bound for a Chip Firing Game on Graphs
- Primer for the algebraic geometry of sandpiles
- Remarks on Hamiltonian properties of powers of digraphs
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Riemann-Roch for sub-lattices of the root lattice \(A_n\)
- Self-organized critical state of sandpile automaton models
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
Cited in
(17)- Generalized ARRIVAL problem for rotor walks in path multigraphs
- Abelian networks IV. Dynamics of nonhalting networks
- Algorithmic aspects of rotor-routing and the notion of linear equivalence
- Random integral matrices: universality of surjectivity and the cokernel
- Mixing time and eigenvalues of the abelian sandpile Markov chain
- Multi-Eulerian tours of directed graphs
- On the complexity of the chip-firing reachability problem
- Chip-firing based methods in the Riemann-Roch theory of directed graphs
- Codeterminantal graphs
- Abelian networks. II: Halting on all inputs
- The distribution of sandpile groups of random regular graphs
- Abelian logic gates
- Rotor-routing reachability is easy, chip-firing reachability is hard
- Root system chip-firing. I: Interval-firing
- scientific article; zbMATH DE number 37833 (Why is no real title available?)
- Abelian networks. I: Foundations and examples
- Sandpile groups and the coeulerian property for random directed graphs
This page was built for publication: CoEulerian graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802106)
