TOPICS
Search

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 t, in round t+1, each of its unburned neighbors becomes burned. The process ends when all nodes are burned. The burning number of a graph G, written by b(G) (Bonato et al. 2014) or bn(G) (Gautam et al. 2020), is then defined as the minimum number of rounds needed for the process to end.

Burning

The process is illustrated above for the path graph P_4 (for which b(P_4)=2) and the the complete bipartite graph K_(2,3) (for which b(K_(2,3))=2).

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

 b(G)<=CL(G),
(1)

where CL(G) 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 G with vertex count n,

 b(G)<=[sqrt(n)],
(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

 b(G)<=[(-3+sqrt(24n+33))/4]
(3)

(Land and Lu 2016, Bonato 2020).

For any connected graph G with graph radius r and graph diameter d,

 [sqrt(d+1)]<=b(G)<=r+1
(4)

(Bonato 2015, Bonato 2020).

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

 4<=b(G)+b(G^_)<=n+2.
(5)

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


See also

Cooling Number, Percolation

Explore with Wolfram|Alpha

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.Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D. R.; and Roshanbin, E. "Burning a Graph Is Hard." Disc. Appl. Math. 232, 73-87, 2017.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.Bonato, A.; Marbach, T. G.; Milne, H.; and Mishura, T. "How to Cool a Graph." https://arxiv.org/abs/2401.03496. 7 Jan 2024.Gautam, R. K.; Kare, A. S.; and Bhavani, S. D. "Faster Heuristics for Graph Burning." Appl. Intelligence 52, 1351-1361, 2021.Land, M. and Lu, L. "An Upper Bound on Burning Number of Graphs." In Proceedings of WAW'16. 2016.

Cite this as:

Weisstein, Eric W. "Burning Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BurningNumber.html

Subject classifications