Toppling numbers of complete and random graphs
Anthony Bonato, William B. Kinnersley, Paweł Prałat
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 toppling
number of a graph G, and is denoted by
t(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 0.596400 n2 < t(Kn)
< 0.637152 n2. 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
pn ≥n^2 / √ log(n)
asymptotically almost surely
t(G(n,p))=(1+o(1)) p t(Kn).
Full Text: PDF PostScript