Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, Bonato et al. [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,\ldots,x_k\) such that for every vertex \(u\) of \(G\), there is some \(i\in \{ 1,\ldots,k\}\) with \({\rm dist}_G(u,x_i)\leq k-i\), and \({\rm dist}_G(x_i,x_j)\geq j-i\) for every \(i,j\in \{ 1,\ldots,k\}\). For a connected graph \(G\) of order \(n\), they prove \(b(G)\leq 2\left\lceil\sqrt{n}\right\rceil-1\), and conjecture \(b(G)\leq \left\lceil\sqrt{n}\right\rceil\). We show that \(b(G)\leq \sqrt{\frac{32}{19}\cdot \frac{n}{1-\epsilon}}+\sqrt{\frac{27}{19\epsilon}}\) and \(b(G)\leq \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_{\geq 3}\) vertices of degree at least \(3\), we show \(b(T)\leq \left\lceil\sqrt{(n+n_2)+\frac{1}{4}}+\frac{1}{2}\right\rceil\) and \(b(T)\leq \left\lceil\sqrt{n}\right\rceil+n_{\geq 3}\). We describe a polynomial time approximation algorithm with approximation factor \(3\) for general graphs. Finally, we show that the problem of deciding whether \(b(G)\leq k\) for a given graph \(G\) and a given integer \(k\) is NP-complete even when restricting the graphs \(G\) to either the unions of paths or to trees that have exactly one vertex of degree at least \(3\).
