Burning Number

Bonato et al. (2014, 2015) defined the burning number of a simple 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 , is then defined as the minimum number of rounds needed for the process to end.

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

(1)

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

(2)

(Land and Lu 2016, Bonato 2020).

For any graph  with graph radius  and graph diameter ,

(3)

(Bonato 2020).

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

family
cocktail party graph	2
crown graph	3
cycle graph
empty graph
gear graph	3
helm graph	3
ladder rung graph
odd graph
path graph
rook graph	3
star graph
sun graph	3
transposition graph
wheel graph	2

In addition, the hypercube graph  satisfies  up to at least . The Möbius ladder agrees with AA155934 up to at least .

Bonato et al. (2015) show that

(4)

where  is the graph diameter and  is the graph radius of a graph  as well as that graph complement of , then

(5)

if  is the graph complement of .

REFERENCES

Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D.; and Roshanbin, E. "Bounds on the Burning Number." 2 Nov 2016. https://arxiv.org/abs/1511.06023.

Bonato, S. "A Survey of Graph Burning." 22 Sep 2020. https://arxiv.org/abs/2009.10642v1.

Bonato, A.; Janssen, J.; and Roshanbin, E. "Burning a Graph as a Model of Social Contagion." In Algorithms and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (

Ed. A. Bonato A., F. Graham F., and P. Prałat). Springer, pp. 13-22, 2014.

Bonato, A.; Janssen, J.; and Roshanbin, E. "How to Burn a Graph." To appear in Internet Mathematics. 23 Jul 2015. https://arxiv.org/abs/1507.06524.

Land, M. and Lu, L. "An Upper Bound on Burning Number of Graphs." In Proceedings of WAW'16. 2016.