Toppling numbers of complete and random graphs

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² / √ log(n) asymptotically almost surely t(G(n,p))=(1+o(1)) p t(Kn).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.229--251
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01188898
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:01
Dernière modification le : vendredi 1 juin 2018 - 19:06:04
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:41:11

Fichier

dmtcs-16-3-13.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188898, version 1

Collections

Citation

Anthony Bonato, William B. Kinnersley, Pawel Pralat. Toppling numbers of complete and random graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.229--251. 〈hal-01188898〉

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

123