On the Burning Game: Nordhaus-Gaddum Bounds and Graph Products

Abstract

We continue research on the burning game on graphs. Given a graph $G$, two players, Burner and Staller, take turns in selecting vertices of $G$ to burn. All burned vertices spread fire to unburned neighboring vertices, as in the burning process. The goal of Burner is to burn the graph 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_{\rm g}(G)$ if Burner makes the first move, and the Staller-start game burning number $b_{\rm g}'(G)$ if Staller starts. In this paper, we study this game further, establishing Nordhaus-Gaddum bounds on the game burning number, as well as bounds for four different types of graph products: strong, Cartesian, lexicographic and corona products.