Chip-firing game and a partial Tutte polynomial for Eulerian digraphs

zbMath1335.91023arXiv1306.0294MaRDI QIDQ276208

Kévin Perrot, Trung van Pham

Publication date: 3 May 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomialchip-firing gamecritical configurationEulerian digraphfeedback arc setrecurrent configurationreliability polynomialsandpile model

Mathematics Subject Classification ID

Graph polynomials (05C31) Games involving graphs (91A43) Directed graphs (digraphs), tournaments (05C20) Combinatorial games (91A46) Eulerian and Hamiltonian graphs (05C45) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (6)

Abelian sandpile model and Biggs-Merino polynomial for directed graphs ⋮ Root polytopes and Jaeger‐type dissections for directed graphs ⋮ A maximizing characteristic for critical configurations of chip-firing games on digraphs ⋮ Threshold state and a conjecture of Poghosyan, Poghosyan, Priezzhev and Ruelle ⋮ \#P-completeness of counting update digraphs, cacti, and series-parallel decomposition method ⋮ Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chip-firing games on directed graphs
• Chip-firing games on graphs
• Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
• Chip-firing and the critical group of a graph
• A Tutte polynomial for partially ordered sets
• Chip firing and the Tutte polynomial
• The sand-pile model and Tutte polynomials
• Classes of lattices induced by chip firing (and sandpile) dynamics.
• On the cover polynomial of a digraph
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• Lattices generated by chip firing game models: criteria and recognition algorithms
• Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
• Acyclic orientations of graphs
• The chip-firing game
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• A Contribution to the Theory of Chromatic Polynomials
• Acyclic orientations and the chromatic polynomial

This page was built for publication: Chip-firing game and a partial Tutte polynomial for Eulerian digraphs