The Burning Number Conjecture Holds Asymptotically

arXiv2207.04035MaRDI QIDQ6404432FDOQ6404432

Authors: Serguei Norine, Jérémie Turcotte 

Publication date: 8 July 2022

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)leqleftlceilsqrtnightceil$ for all graphs $G$ on $n$ vertices. We prove that this conjecture holds asymptotically, that is $b(G)leq(1+o(1))sqrtn$.

Mathematics Subject Classification ID

Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Games on graphs (graph-theoretic aspects) (05C57)

This page was built for publication: The Burning Number Conjecture Holds Asymptotically

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404432)