The Burning Number Conjecture Holds Asymptotically

Abstract

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)\le \lceil \sqrt{n}\rceil$ for all graphs $G$ on $n$ vertices. We prove that this conjecture holds asymptotically, that is $b(G)\le (1+o(1))\sqrt{n}$.

18 pages

Cited by in corpus (2)

• Adversarial graph burning densities
• A Note on Graph Burning of Path Forests