# Smash and Grab: the 0.6 Scoring Game on Graphs

2 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
3 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : In this paper, we introduce and study a new scoring game on graphs called SMASH AND GRAB. In this game, two players, called Left and Right, take turns removing a vertex of the graph as well as all of its neighbours that become isolated by this removal. For each player and each of their turns, they score the number of vertices that were removed on their turn. The game ends when there are no more vertices remaining, and the player with the highest final score wins. We denote by $Ls(G)$ the difference between Left and Right's final scores in $G$ when Left starts and both players play optimally (they both aim to maximise their scores). We mainly study this parameter for different graph classes. We notably prove that $Ls(F) ≥ 0$ for any forest $F$ (i.e., the first player cannot lose). We then use this result to compute the exact value of $Ls(G)$ for particular forests such as unions of paths and subdivided stars. The result in paths then solves the case of a unique cycle. Finally, we prove that, for a generalisation of the game, computing the score is PSPACE-complete.
Keywords :
Document type :
Preprints, Working Papers, ...

https://hal.archives-ouvertes.fr/hal-03371099
Contributor : Fionn Mc Inerney Connect in order to contact the contributor
Submitted on : Friday, October 8, 2021 - 1:16:23 PM
Last modification on : Thursday, November 11, 2021 - 3:46:03 PM

### File

Scoring0_6.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03371099, version 1

### Citation

Éric Duchêne, Valentin Gledel, Sylvain Gravier, Fionn Mc Inerney, Mehdi Mhalla, et al.. Smash and Grab: the 0.6 Scoring Game on Graphs. 2021. ⟨hal-03371099⟩

Record views