The Burning Number Conjecture Holds Asymptotically

2022/07/08 by Norin, Sergey, Turcotte, Jérémie · 2 citations
#05C05 (Secondary) #05C57 (Primary) 05C82 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2207.04035

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

Cited by

• The burning number conjecture holds for trees of order n with at most \lfloor √(n-1)\rfloor degree-2 vertices
• Random burning of the Euclidean lattice

Related

• Improved pyrotechnics : Closer to the burning graph conjecture
• An improved bound on the burning number of graphs
• An Upper Bound on Burning Number of Graphs
• Finding a good tree to burn
• Bounds on the Burning Number