  Graph burning models the propagation of information within a network as a
stepwise process where at each step, one node becomes informed, and this
information also spreads to all neighbors of previously informed nodes.
Formally, graph burning is defined as follows: For an undirected graph $G$, at
step $t=0$ all vertices in $G$ are unburned. At each step $t\ge 1$, one new
unburned vertex is selected to burn if such a vertex exists. If a vertex is
burned at step $t$, then all its unburned neighbors are burned in step $t+1$,
and the process continues until there are no unburned vertices in $G$. The
burning number of a graph $G$, denoted by $b(G)$, is the minimum number of
steps required to burn all the vertices of $G$. The burning number problem asks
whether the burning number of an input graph $G$ is at most $k$ or not. In this
paper, we study the burning number problem both from an algorithmic and a
structural point of view. The burning number problem 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 cubic graphs
and connected proper interval graphs. The well-known burning number conjecture
asserts that all the vertices of a 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 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
algorithmic complexity of these variants.
