An Upper Bound on Burning Number of Graphs

Abstract

The burning number $b(G)$ of a graph $G$ was introduced by Bonato, Janssen, and Roshanbin [Lecture Notes in Computer Science 8882 (2014)] for measuring the speed of the spread of contagion in a graph. They proved for any connected graph $G$ of order $n$, $b(G)\le 2\lceil \sqrt{n}\rceil -1$, and conjectured that $b(G)\le \lceil \sqrt{n}\rceil$. In this paper, we proved $b(G)\le \lceil \frac{-3+\sqrt{24n+33}}{4}\rceil$, which is roughly $\frac{\sqrt{6}}{2}\sqrt{n}$. We also settled the following conjecture of Bonato-Janssen-Roshanbin: $b(G)b(\bar{G})\le n+4$ provided both $G$ and $\bar{G}$ are connected.

Cited by in corpus (1)

• An improved bound on the burning number of graphs