CoEulerian graphs

DOI10.1090/PROC/12952zbMATH Open1334.05025arXiv1502.04690OpenAlexW3037947434MaRDI QIDQ2802106FDOQ2802106

Matthew Farrell, Lionel Levine

Publication date: 25 April 2016

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1502.04690

Recommendations

• On the complexity of the chip-firing reachability problem
• Chip-firing games on graphs
• Chip-firing games on directed graphs
• No Polynomial Bound for the Chip Firing Game on Directed Graphs
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs

zbMATH Keywords

Eulerian digraphcritical grouporiented spanning treeperiod vectorPham indexLaplacian latticesandpile groupchip-firing

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Primer for the algebraic geometry of sandpiles
• Self-organized critical state of sandpile automaton models
• Chip-firing games on graphs
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• Chip-firing games on directed graphs
• Chip-firing and Riemann-Roch theory for directed graphs
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Chip-Firing and Rotor-Routing on Directed Graphs
• Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
• Asymmetric Abelian sandpile models
• Abelian networks. I: Foundations and examples
• Abelian networks. II: Halting on all inputs
• Asymptotically Fast Triangularization of Matrices over Rings
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• Polynomial Bound for a Chip Firing Game on Graphs
• No Polynomial Bound for the Chip Firing Game on Directed Graphs
• Title not available (Why is that?)
• Remarks on Hamiltonian properties of powers of digraphs
• Abelian sandpile model and Biggs-Merino polynomial for directed graphs
• Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
• Centers of directed cacti

Cited In (17)

• Random integral matrices: universality of surjectivity and the cokernel
• Multi-Eulerian tours of directed graphs
• The distribution of sandpile groups of random regular graphs
• Root system chip-firing. I: Interval-firing
• On the complexity of the chip-firing reachability problem
• Abelian networks. II: Halting on all inputs
• Codeterminantal graphs
• Generalized ARRIVAL problem for rotor walks in path multigraphs
• Rotor-routing reachability is easy, chip-firing reachability is hard
• Title not available (Why is that?)
• Algorithmic aspects of rotor-routing and the notion of linear equivalence
• Abelian networks. I: Foundations and examples
• Abelian networks IV. Dynamics of nonhalting networks
• Mixing time and eigenvalues of the abelian sandpile Markov chain
• Sandpile groups and the coeulerian property for random directed graphs
• Abelian Logic Gates
• Chip-firing based methods in the Riemann-Roch theory of 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)