Summary: Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, A. Bonato et al. [Lect. Notes Comput. Sci. 8882, 13–22 (2014; Zbl 1342.05154)] 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 \(\operatorname{dist}_G(u,x_i)\leq k-i\), and \(\operatorname{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 that \(b(G)\leq 2\lceil\sqrt{n}\rceil-1\), and conjecture \(b(G)\leq\lceil\sqrt{n}\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_{\geq3}\) vertices of degree at least 3, we show \(b(T)\leq\lceil\sqrt{(n+n_2)+\frac{1}{4}}+\frac{1}{2}\rceil\) and \(b(T)\leq\lceil\sqrt{n}\rceil+n_{\geq3}\). Furthermore, we characterize the binary trees of depth \(r\) that have burning number \(r+1\).