Toppling numbers of complete and random graphs

MaRDI QIDQ5173157zbMATH OpenFDO

Authors Anthony Bonato, William B. Kinnersley, Paweł Prałat

Publication date 9 February 2015

Full work available at URL https://arxiv.org/abs/1305.1677, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2357/0.html

zbMATH Keywords

abelian sandpile modelchip-firing gametoppling game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) 2-person games (91A05) Games involving graphs (91A43)

Abstract: We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accumulates as many chips as its degree, it fires, sending one chip to each neighbour; this may in turn cause other vertices to fire. The game ends when vertices continue firing forever. Min seeks to minimize the number of chips played during the game, while Max seeks to maximize it. When both players play optimally, the length of the game is the {em toppling number} of a graph $G$, and is denoted by $g(G)$. By considering strategies for both players and investigating the evolution of the game with differential equations, we provide asymptotic bounds on the toppling number of the complete graph. In particular, we prove that for sufficiently large $n$ ${\displaystyle }$0.596400 n^2 < g(K_n) < 0.637152 n^2.${\displaystyle }$ Using a fractional version of the game, we couple the toppling numbers of complete graphs and the binomial random graph $G(n,p)$. It is shown that for $pnge{n}^{2/sqrtlogn}$ asymptotically almost surely $t(G(n,p))=(1+o(1))pg(K_n)$.

Recommendations

• Chip-firing games on graphs
• Properties of chip-firing games on complete graphs
• Polynomial Bound for a Chip Firing Game on Graphs
• No Polynomial Bound for the Chip Firing Game on Directed Graphs
• Algorithmic aspects of a chip-firing game

Cited in

(9)

• European tenure games
• Toppling on permutations with an extra chip
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Game brush number
• Bounds on the game transversal number in hypergraphs
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• scientific article; zbMATH DE number 2086679 (Why is no real title available?)
• Paired-domination game played in graphs
• An upper bound on the extremal version of Hajnal's triangle-free game

This page was built for publication: Toppling numbers of complete and random graphs

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