An improved bound on the burning number of graphs

Abstract

The burning number conjecture states that the burning number of a connected graph is at most $\lceil \sqrt{n}\rceil .$ While the conjecture is unresolved, Land and Lu proved that the burning number of a connected graph is at most $\sqrt{(3/2)n}+O(1).$ Using an algorithmic approach, we provide an improved upper bound for the burning number of a connected graph: $$\lceil \frac{\sqrt{12n+64}+8}{3}\rceil =\sqrt{(4/3)n}+O(1).$$

arXiv admin note: text overlap with arXiv:2009.10642

References in corpus (1)

• An Upper Bound on Burning Number of Graphs