Graph Burning: Bounds and Hardness

The burning number of a graph $G$, denoted by $b(G)$, is the minimum number of steps required to burn all the vertices of a graph where in each step the existing fire spreads to all the adjacent vertices and one additional vertex can be burned as a new fire source. In this paper, we study the burning number problem both from an algorithmic and a structural point of view. The decision problem of computing the burning number of an input graph is known to be NP-Complete for trees with maximum degree at most three and interval graphs. Here, we prove that this problem is NP-Complete even when restricted to connected proper interval graphs and connected cubic graphs. The well-known burning number conjecture asserts that all the vertices of any graph of order $n$ can be burned in $\lceil \sqrt{n}~\rceil$ steps. In line with this conjecture, upper and lower bounds of $b(G)$ are well-studied for various special graph classes. Here, we provide an improved upper bound for the burning number of connected $P_k$-free graphs and show that the bound is tight up to an additive constant $1$. Finally, we study two variants of the problem, namely edge burning (only edges are burned) and total burning (both vertices and edges are burned). In particular, we establish their relationship with the burning number problem and evaluate the complexity of these variants.