Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
From MaRDI portal
(Redirected from Publication:276208)
Abstract: The Chip-firing game is a discrete dynamical system played on a graph, in which chips move along edges according to a simple local rule. Properties of the underlying graph are of course useful to the understanding of the game, but since a conjecture of Biggs that was proved by Merino L'opez, we also know that the study of the Chip-firing game can give insights on the graph. In particular, a strong relation between the partial Tutte polynomial and the set of recurrent configurations of a Chip-firing game (with a distinguished sink vertex) has been established for undirected graphs. A direct consequence is that the generating function of the set of recurrent configurations is independent of the choice of the sink for the game, as it characterizes the underlying graph itself. In this paper we prove that this property also holds for Eulerian directed graphs (digraphs), a class on the way from undirected graphs to general digraphs. It turns out from this property that the generating function of the set of recurrent configurations of an Eulerian digraph is a natural and convincing candidate for generalizing the partial Tutte polynomial to this class. Our work also gives some promising directions of looking for a generalization of the Tutte polynomial to general digraphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 4134043 (Why is no real title available?)
- scientific article; zbMATH DE number 67324 (Why is no real title available?)
- scientific article; zbMATH DE number 1741026 (Why is no real title available?)
- A Contribution to the Theory of Chromatic Polynomials
- A Tutte polynomial for partially ordered sets
- Acyclic orientations and the chromatic polynomial
- Acyclic orientations of graphs
- Chip firing and the Tutte polynomial
- Chip-firing and the critical group of a graph
- Chip-firing games on directed graphs
- Chip-firing games on graphs
- Classes of lattices induced by chip firing (and sandpile) dynamics.
- Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
- Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
- Lattices generated by chip firing game models: criteria and recognition algorithms
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
- On the cover polynomial of a digraph
- The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
- The chip-firing game
- The sand-pile model and Tutte polynomials
Cited in
(11)- \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method
- Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
- Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle
- scientific article; zbMATH DE number 1741027 (Why is no real title available?)
- Minimal recurrent configurations of chip firing games and directed acyclic graphs
- Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
- A maximizing characteristic for critical configurations of chip-firing games on digraphs
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- CoEulerian graphs
- Root polytopes and Jaeger‐type dissections for directed graphs
- A geometric proof for the root-independence of the greedoid polynomial of Eulerian branching greedoids
This page was built for publication: Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q276208)
