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

zbMATH Open1335.91023arXiv1306.0294MaRDI QIDQ276208FDOQ276208

Authors: Kévin Perrot, Trung van Pham 

Publication date: 3 May 2016

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

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 $T_G(1,y)$ 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 $T_G(1,y)$ to this class. Our work also gives some promising directions of looking for a generalization of the Tutte polynomial to general digraphs.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Chip firing and the Tutte polynomial
• The chip-firing game
• Chip-firing games on directed graphs
• The chip-firing game and the sandpile model
• Chip-firing games on graphs

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• A Contribution to the Theory of Chromatic Polynomials
• Chip-firing and the critical group of a graph
• Chip firing and the Tutte polynomial
• The sand-pile model and Tutte polynomials
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Title not available (Why is that?)
• Chip-firing games on graphs
• Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
• Acyclic orientations of graphs
• A Tutte polynomial for partially ordered sets
• 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
• The chip-firing game
• Title not available (Why is that?)
• Title not available (Why is that?)
• Acyclic orientations and the chromatic polynomial
• Chip-firing games on directed graphs

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
• Title not available (Why is that?)
• 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)