Burning Number

Bonato et al. (2014, 2015) defined the burning number of a finite, simple, undirected graph as follows. Consider a process called burning involving are discrete time steps. Each node is either burned or unburned; if a node is burned, then it remains in that state until the end of the process. In every round, choose one additional unburned node to burn (if such a node is available). Once a node is burned in round , in round , each of its unburned neighbors becomes burned. The process ends when all nodes are burned. The burning number of a graph , written by (Bonato et al. 2014) or (Gautam et al. 2020), is then defined as the minimum number of rounds needed for the process to end.

The process is illustrated above for the path graph (for which ) and complete bipartite graph (for which ).

The decision version of the graph burning problem is NP-complete (Bessy et al. 2017). The burning number problem on disconnected graphs is harder than on connected graphs (Gautam et al. 2021). This is because in a disconnected graph, you can start fires in the larger connected components early and let those fires propagate on their own while fires setting on smaller components.

By construction, the burning number satisfies

(1)

where is the cooling number. This is because burning number corresponds to the first iteration in which a completely burnt graph first occurs, while the cooling number corresponds to the iteration in which no partially-uncooled graph remains.

Bonato et al. (2015) showed that for a traceable graph with vertex count ,

(2)

and conjecture that this inequality holds for any connected graph. Bonato (2020) calls this statement the "burning number conjecture," and terms any graph that satisfies the inequality "well-burnable." The best known upper bound is given by

(3)

(Land and Lu 2016, Bonato 2020).

For any connected graph with graph radius and graph diameter ,

(4)

(Bonato 2015, Bonato 2020).

Bonato et al. (2015) show that for the graph complement of ,

(5)

Values for some parametrized families of graphs are summarized below, where denotes the ceiling function.

family
antiprism graph
cocktail party graph	2
crown graph	3
cycle graph
empty graph
gear graph	3
helm graph	3
hypercube graph
king graph
ladder graph
ladder rung graph
Möbius ladder
odd graph
path graph
prism graph
rook graph	3
star graph
sun graph	3
torus grid graph
transposition graph
wheel graph	2