Chip-firing games on graphs

DOI10.1016/S0195-6698(13)80111-4zbMath0729.05048OpenAlexW2082513731MaRDI QIDQ805639

László Lovász, Anders Bjoerner, Peter W. Shor

Publication date: 1991

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0195-6698(13)80111-4

zbMATH Keywords

graph degree game number of edges terminating configuration

Mathematics Subject Classification ID

Integer programming (90C10) Graph theory (05C99)

Related Items

Discrete and metric divisorial gonality can be different, Chip-firing game and a partial Tutte polynomial for Eulerian digraphs, Dynamic graph models and their properties, On extreme points of the diffusion polytope, Divisors on graphs, binomial and monomial ideals, and cellular resolutions, Game brush number, Sandpile models and lattices: a comprehensive survey, Brushing with additional cleaning restrictions, Root system chip-firing, The numbers game and Coxeter groups, No polynomial bound for the period of the parallel chip firing game on graphs, Riemann-Roch and Abel-Jacobi theory on a finite graph, On the sandpile group of regular trees, Spectrally optimized pointset configurations, Chip-firing groups of iterated cones, Enumerating degree sequences in digraphs and a cycle--cocycle reversing system, Abelian sandpile model and Biggs-Merino polynomial for directed graphs, Chip firing and the Tutte polynomial, \textsc{polish} -- Let us play the cleaning game, Universality of the chip-firing game, Chip-firing based methods in the Riemann-Roch theory of directed graphs, The sand-pile model and Tutte polynomials, Computing linear systems on metric graphs, Classes of lattices induced by chip firing (and sandpile) dynamics., The Bhargava greedoid, Results in labeled chip-firing, Treewidth is a lower bound on graph gonality, Abelian networks. II: Halting on all inputs, Critical groups of simplicial complexes, Compatible recurrent identities of the sandpile group and maximal stable configurations, Combinatorial aspects of sandpile models on wheel and Fan graphs, Two sided Sand Piles Model and unimodal sequences, Fixed-point forms of the parallel symmetric sandpile model, Brushing without capacity restrictions, On enumeration of conjugacy classes of Coxeter elements, Cleaning a network with brushes, The Riemann–Roch strategy, ULD-Lattices and Δ-Bonds, No Polynomial Bound for the Chip Firing Game on Directed Graphs, Spanning trees and recurrent configurations of a graph, Integral flow and cycle chip-firing on graphs, Characterizing immutable sandpiles: a first look, Strict partitions and discrete dynamical systems, The Potts model and the Tutte polynomial, Parallel chip-firing on the complete graph: Devil’s staircase and Poincaré rotation number, Riemann-Roch theory for graph orientations, Chip-firing games on directed graphs, Markov chain methods for analyzing urban networks, A note on the Abelian sandpile in \(\mathbb Z^d\), Strong emergence of wave patterns on Kadanoff sandpiles, On the sandpile group of the graph \(K_{3}\times C_n\), Growth rates and explosions in sandpiles, Mean curvature, threshold dynamics, and phase field theory on finite graphs, \(G\)-parking functions, acyclic orientations and spanning trees, Computing graph gonality is hard, Parallel cleaning of a network with brushes, Chip-firing and energy minimization on M-matrices, On graph parameters guaranteeing fast sandpile diffusion, Characterizations of polygreedoids and poly-antimatroids by greedy algorithms, A constant bound for the periods of parallel chip-firing games with many chips, The abelian sandpile model on randomly rooted graphs and self-similar groups, Goldbug variations, The sandpile group of a family of nearly complete graphs, Random walks and flights over connected graphs and complex networks, The sandpile model on \(K_{m,n}\) and the rank of its configurations, CoEulerian graphs, Resource network with limited capacity of attractor vertices, Abelian Networks I. Foundations and Examples, A maximizing characteristic for critical configurations of chip-firing games on digraphs, Hall-Littlewood symmetric functions via the chip-firing game, Chip Firing on General Invertible Matrices, The chip firing game on \(n\)-cycles, On the Complexity of Sandpile Prediction Problems, Properties of chip-firing games on complete graphs, Enumerative questions on rooted weighted necklaces, The sandpile group of a tree, The Tutte polynomial as a growth function, Confluence in labeled chip-firing, An Essay on the Riemann Hypothesis, Root system chip-firing. I: Interval-firing, Rotor-routing reachability is easy, chip-firing reachability is hard, On the sandpile group of dual graphs, Chip-firing and the critical group of a graph, On the scramble number of graphs, Recognition of Antimatroidal Point Sets, Source reversal and chip firing on graphs, Brill-Noether conjecture on cactus graphs, A geometric approach to acyclic orientations, Discrete balayage and boundary sandpile, An exact bound on the number of chips of parallel chip-firing games that stabilize, A survey on the stability of (extended) linear Sand Pile model, Distributive Lattice Polyhedra, The chip-firing game, Directed nonabelian sandpile models on trees, Coding distributive lattices with Edge Firing Games., A Geometric Characterization of Poly-antimatroids, Polynomial ideals for sandpiles and their Gröbner bases, On computation of Baker and Norine's rank on complete graphs, Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph, Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs, The distribution of sandpile groups of random graphs, “Pass the Buck” on a Complete Binary Tree, Toppleable permutations, excedances and acyclic orientations, The sandpile group of a thick cycle graph, Abelian networks IV. Dynamics of nonhalting networks, Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three, Unnamed Item, Finite record sets of chip-firing games, “Pass the Buck” on a Rooted Tree, A greedy chip‐firing game, On approximating the rank of graph divisors, On a relationship between the characteristic and matching polynomials of a uniform hypertree, Laplacian growth, sandpiles, and scaling limits, Algebraic Properties of Generalized Graph Laplacians: Resistor Networks, Critical Groups, and Homological Algebra, Height probabilities in the Abelian sandpile model on the generalized finite Bethe lattice, Passing the Buck and Firing Fibonacci: Adventures with the Stochastic Abacus, Unnamed Item, Sorting via chip-firing, Recognizing hyperelliptic graphs in polynomial time, Sorting via chip-firing, Enumerating linear systems on graphs, Random Walks, Electric Networks and The Transience Class problem of Sandpiles, Mixing time and eigenvalues of the abelian sandpile Markov chain, Unnamed Item, On the complexity of the chip-firing reachability problem

Cites Work