The Burning Number Conjecture Holds Asymptotically

07/08/2022
by   Sergey Norin, et al.
0

The burning number b(G) of a graph G is the smallest number of turns required to burn all vertices of a graph if at every turn a new fire is started and existing fires spread to all adjacent vertices. The Burning Number Conjecture of Bonato et al. (2016) postulates that b(G)≤⌈√(n)⌉ for all graphs G on n vertices. We prove that this conjecture holds asymptotically, that is b(G)≤ (1+o(1))√(n).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset