A maximizing characteristic for critical configurations of chip-firing games on digraphs

DOI10.1016/J.DAM.2018.05.005zbMATH Open1398.05136arXiv1711.10805OpenAlexW2963316570WikidataQ129748120 ScholiaQ129748120MaRDI QIDQ1801042FDOQ1801042

Authors: Hoang Thach Nguyen, Thi Thu Huong Tran 

Publication date: 26 October 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Aval et al. proved that starting from a critical configuration of a chip- firing game on an undirected graph, one can never achieve a stable configuration by reverse firing any non-empty subsets of its vertices. In this paper, we generalize the result to digraphs with a global sink where reverse firing subsets of vertices is replaced with reverse firing multi-subsets of vertices. Consequently, a combinatorial proof for the duality between critical configurations and superstable configurations on digraphs is given. Finally, by introducing the concept of energy vector assigned to each configuration, we show that critical and superstable configurations are the unique ones with the greatest and smallest (w.r.t. the containment order), respectively, energy vectors in each of their equivalence classes.

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

Recommendations

• Order structure and energy of conflicting chip firing game
• Algorithmic aspects of a chip-firing game
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
• Chip-firing and energy minimization on M-matrices
• Chip-firing games on directed graphs

zbMATH Keywords

dualitycritical configurationschip-firing gamesenergy vector optimizersuperstable configurations

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Chip-firing and the critical group of a graph
• Chip firing and the Tutte polynomial
• Chip-firing games, potential theory on graphs, and spanning trees
• 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
• M-matrix characterizations. I: nonsingular M-matrices
• The chip-firing game
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
• Chip-firing games on directed graphs
• Chip-firing and Riemann-Roch theory for directed graphs
• Chip-Firing and Rotor-Routing on Directed Graphs
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Asymmetric Abelian sandpile models
• Chip-firing and energy minimization on M-matrices
• Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma
• The lattice structure of chip firing games and related models
• Signed chip firing games and symmetric sandpile models on the cycles

Cited In (1)

• Order structure and energy of conflicting chip firing game

This page was built for publication: A maximizing characteristic for critical configurations of chip-firing games on digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801042)