Bounds on the Burning Number

Abstract

Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, Bonato, Janssen, and Roshanbin [Burning a Graph as a Model of Social Contagion, Lecture Notes in Computer Science 8882 (2014) 13-22] define the burning number $b(G)$ of a graph $G$ as the smallest integer $k$ for which there are vertices $x_1,\dots ,x_k$ such that for every vertex $u$ of $G$, there is some $i\in \{1,\dots ,k\}$ with ${\mathrm{dist}}_G(u,x_i)\le k-i$, and ${\mathrm{dist}}_G(x_i,x_j)\ge j-i$ for every $i,j\in \{1,\dots ,k\}$. For a connected graph $G$ of order $n$, they prove that $b(G)\le 2\lceil \sqrt{n}\rceil -1$, and conjecture $b(G)\le \lceil \sqrt{n}\rceil$. We show that $b(G)\le \sqrt{\frac{32}{19}\cdot \frac{n}{1-\epsilon }}+\sqrt{\frac{27}{19\epsilon }}$ and $b(G)\le \sqrt{\frac{12n}{7}}+3\approx 1.309\sqrt{n}+3$ for every connected graph $G$ of order $n$ and every $0<\epsilon <1$. For a tree $T$ of order $n$ with $n_2$ vertices of degree $2$, and $n_{\ge 3}$ vertices of degree at least $3$, we show $b(T)\le \lceil \sqrt{(n+n_2)+\frac{1}{4}}+\frac{1}{2}\rceil$ and $b(T)\le \lceil \sqrt{n}\rceil +n_{\ge 3}$. Furthermore, we characterize the binary trees of depth $r$ that have burning number $r+1$.