The burning game on graphs

Abstract

Motivated by the burning and cooling processes, the burning game is introduced. Two players (Burner and Staller) play the game on a graph $G$ by alternately selecting vertices of $G$ to burn; as in the burning process, burning vertices spread fire to unburned neighbors. Burner aims to burn all vertices of $G$ as quickly as possible, while Staller wants the process to last as long as possible. If both players play optimally, then the number of time steps needed to burn the whole graph $G$ is the game burning number $b_{\mathrm{g}}(G)$ if Burner makes the first move, and the Staller-start game burning number $b_{\mathrm{g}}^{\prime }(G)$ if Staller starts. In this paper, basic bounds on $b_{\mathrm{g}}(G)$ are given and several fundamental properties of the burning game established. Graphs with small game burning numbers are characterized and the game is studied on paths and cycles. An analogue of the burning number conjecture for the burning game is also considered. Finally, it is shown that the problem of determining whether or not $b_{\mathrm{g}}(G)\le k$ is NP-hard.

arXiv commentThis is the replacement of the first version of the file, that was further developed and then split into two papers. The first one, this, is published in Discrete Mathematics, and this is its final version, and the second one, about further results on the burning game, including Nordhaus-Gaddum bounds and bounds for four graph products on the game burning number is uploaded as a new submission