The Burning Number Conjecture Holds Asymptotically

MaRDI QIDQ6404432FDO

Authors Serguei Norine, Jérémie Turcotte

Publication date 8 July 2022

Mathematics Subject Classification ID

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

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$.

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)