20.500.12556/DiRROS-27609 The burning game on graphs 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_g(G)$ if Burner makes the first move, and the Staller-start game burning number $b'_g(G)$ if Staller starts. In this paper, basic bounds on $b_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_g(G) \le k$ is NP-hard. burning game burning number Burner Staller igra gorenja grafa število gorenja požigalec zavlačevalka true false false Angleški jezik Slovenski jezik Neznano 2026-02-16 09:33:23 2026-02-16 09:33:24 2026-02-17 03:50:36 0000-00-00 00:00:00 2026 0 0 16 str. iss. 5, article no. 115027 Vol. 349 May 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-05-01 519.17:519.83 0012-365X 10.1016/j.disc.2026.115027 268412163 1-s2.0-S0012365X26000518-main.pdf 1-s2.0-S0012365X26000518-main.pdf 1 DF60E7C58A690368A53C2CA36CEA2B36 3060837a601417a3653781db8b693f45ef7689db6ec83c3ef37ac0c6d9a27b20 0e8b9c10-0b14-11f1-bcbc-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=40476 https://www.sciencedirect.com/science/article/pii/S0012365X26000518 1 2cd621c6-0b12-11f1-bcbc-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=40475 Inštitut za matematiko, fiziko in mehaniko 0 0 0