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

DOI10.1016/J.DAM.2018.05.005MaRDI QIDQ1801042zbMATHOpenAlexWikidataFDO

Authors Hoang Thach Nguyen, Thi Thu Huong Tran

Publication date 26 October 2018

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

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

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)

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.

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

Cites work

• Asymmetric Abelian sandpile models
• Chip firing and the Tutte polynomial
• Chip-Firing and Rotor-Routing on Directed Graphs
• Chip-firing and Riemann-Roch theory for directed graphs
• Chip-firing and energy minimization on M-matrices
• Chip-firing and the critical group of a graph
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
• Chip-firing games on directed graphs
• Chip-firing games on graphs
• Chip-firing games, potential theory on graphs, and spanning trees
• M-matrix characterizations. I: nonsingular M-matrices
• Primer for the algebraic geometry of sandpiles
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Self-organized critical state of sandpile automaton models
• Signed chip firing games and symmetric sandpile models on the cycles
• The chip-firing game
• The lattice structure of chip firing games and related models
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma

Cited in

(2)

• Order structure and energy of conflicting chip firing game
• Integral flow and cycle chip-firing on graphs

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)