# Improved Pyrotechnics: Closer to the Burning Number Conjecture

Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, Shahin Kamali, Théo Pierron, Mikaël Rabie

► To cite this version:

Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, Shahin Kamali, et al. Improved Pyrotechnics: Closer to the Burning Number Conjecture. The Electronic Journal of Combinatorics, 2023, 30 (4), 10.37236/11113. hal-04587525

HAL Id: hal-04587525

https://hal.science/hal-04587525v1

Submitted on 13 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Improved Pyrotechnics:
Closer to the Burning Number Conjecture

Paul Bastide<sup>*a*</sup>

Marthe Bonamy<sup>*b*</sup>

Anthony Bonato<sup>*c*</sup>

Pierre Charbit<sup>*d*</sup>

Shahin Kamali<sup>*e*</sup>

Théo Pierron<sup>*f*</sup>

Mikaël Rabie<sup>*d*</sup>

Submitted: Mar 14, 2022; Accepted: Jun 9, 2023; Published: Oct 6, 2023

© The authors. Released under the CC BY license (International 4.0).

**Abstract**

The Burning Number Conjecture claims that for every connected graph $G$ of order $n$, its burning number satisfies $b(G) \le \lceil\sqrt{n}\rceil$. While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its *growth*, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n$, given by $b(G) \le \sqrt{4n/3} + 1$, improving on the previously known $\sqrt{3n/2} + O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least 3 and holds for all large enough graphs with minimum degree at least 4. The previous best-known result was for graphs with minimum degree 23.

**Mathematics Subject Classifications:** 05C05, 05C12

# 1 Introduction

Graph burning is a simplified model for the spread of influence in a network. Associated with the process is a parameter introduced in [BJR14, BJR16, Ros16], the burning number, which quantifies the speed at which the influence spreads to every vertex. Graph burning is defined as follows. Given a graph $G$, the burning process on $G$ is a discrete-time process. At the beginning of the first round, all vertices are unburned. In each round, first all unburned vertices that have a burned neighbour become burned, and then one new unburned vertex is chosen to burn, if such a vertex is available. If at the end of round

<footnote><sup>*a*</sup>École Normale Supérieure Rennes, Rennes, France</footnote>

<footnote><sup>*b*</sup>CNRS, LaBRI, Université de Bordeaux, Bordeaux, France</footnote>

<footnote><sup>*c*</sup>Ryerson University, Toronto, Canada</footnote>

<footnote><sup>*d*</sup>IRIF, Paris, Paris, France</footnote>

<footnote><sup>*e*</sup>University of Manitoba, Winnipeg, Canada</footnote>

<footnote><sup>*f*</sup>LIRIS, Université de Lyon, Lyon, France</footnote>
k every vertex of G is burned, then G is k-burnable. The burning number of G, written $b(G)$, is defined to be the least k such that G is k-burnable.

As a graph with n isolated vertices is not (n - 1)-burnable, we instead focus on connected graphs. Paths are an interesting special case. For a path $P_n$ on n vertices, it was shown in [BJR16] that $b(P_n) = \lceil \sqrt{n} \rceil$. In [BJR16], it was conjectured that the path on n vertices is one of the graphs with the largest burning number among connected graphs.

**Burning Number Conjecture (or BNC):** For a connected graph G of order n,

$$b(G) \leq \lceil \sqrt{n} \rceil.$$

For any connected graph G and any spanning tree T of G, we have $b(G) \leq b(T)$. Therefore it is sufficient to prove that the conjecture holds for trees.

The BNC has resisted attempts at its resolution, although various upper bounds on the burning number are known. In [BBJ+18], it was proved that for every connected graph G of order n that

$$b(G) \leq \sqrt{\frac{12}{7}n} + 3.$$

These bounds were improved in [LL16], who proved, up until this paper, the best-known upper bound:

$$b(G) \leq \left\lceil \frac{\sqrt{24n + 33} - 3}{4} \right\rceil = \sqrt{\frac{3}{2}n} + O(1).$$

In the present paper, we improve this by showing that any tree of order n can burn in $\sqrt{\frac{4}{3}n} + 1$ rounds.

**Theorem 1.** For a connected graph G of order n, we have that

$$b(G) \leq \left\lceil \sqrt{\frac{4}{3}n} \right\rceil + 1.$$

While the BNC is open for general graphs, it is known to hold for a number of graph classes. For example, in [BL19], it is proven that the conjecture holds for spiders, which are defined as trees with at most one vertex of degree at most 3. In [KMZ20], it was proven that any graph with minimum degree $\delta \geq 23$ satisfy the conjecture. Using Theorem 1, we prove that the conjecture almost holds for all connected graphs of minimum degree at least 3, and also holds for those of minimum degree at least 4 that are of a large enough order.

**Theorem 2.** For any connected graph G on n vertices, if every vertex in G has degree at least 3, then $b(G) \leq \lceil \sqrt{n} \rceil + 2$.

**Theorem 3.** For any connected graph G on n vertices, if every vertex in G has degree at least 4 and n is sufficiently large, then $b(G) \leq \lceil \sqrt{n} \rceil$.
Our second main result concerns trees that have bounded growth. The *growth* of a connected graph *G* is the smallest integer *k* such that all vertices in *G* are within distance *k* of some path *P* in *G*. Trees of growth 1 are known also as the class of *caterpillars* and by extension trees of growth *k* are often referred to as *k-caterpillars*. As proven in Hiller, Triesch, and Koster [HTK19] and independently in [LHH20], caterpillars satisfy the conjecture, and the conjecture has also been confirmed for 2-caterpillars (or *lobsters*) in [HTK19]. We refer the reader to a survey on graph burning for further details [Bon21]. Note that any result on trees of bounded growth immediately applies to graphs of bounded growth, by considering an appropriate spanning tree. We remark that the notion of growth in this context matches that of path-length (see eg [KMZ20]).

In this paper, we present two theorems about trees of bounded growth. The first one states that in order to prove the BNC for *k*-caterpillars, it suffices to verify it for a finite number of them. It would be interesting to find ways to go further and transform this into a practical way for the BNC to be verified for *k*-caterpillars (for say *k* = 10). The statement currently suggests unreasonably many cases, which seems unnecessary.

**Theorem 4.** For any $k \in \mathbb{N}$, if the BNC holds for all $k$-caterpillars on at most $(4k^2 + 5k - 2)^2$ vertices, then it holds for all $k$-caterpillars.

The second gives an approximation of the BNC for all *k*-caterpillars.

**Theorem 5.** For any $k \in \mathbb{N}$ and every tree $T$ of growth at most $k$ on $n$ vertices

$$b(T) \le \sqrt{n + (4k^2 + 5k - 2)^2}.$$

In fact both will be direct consequences of the more general statement below (by taking $c = 0$ or $c = (4k^2 + 5k - 2)^2$).

**Theorem 6.** Let $k$ and $c$ be two integers. If $b(T) \le \sqrt{|V(T)|+c}$ holds for every $k$-caterpillar $T$ of order at most $(4k^2 + 5k - 2)^2 - c$, then it holds for all $k$-caterpillars.

Before closing this introduction, we present a reformulation of the conjecture that we will use in the rest of the paper, and allows us to propose a stronger conjecture. If we denote by $v_i$ the vertex chosen to burn at the end of round $i$ in a burning process, then the set of vertices that are burned after $p$ rounds is simply $\cup_{i=1,...,p} B(v_i, p-i)$ where $B(v,r)$ is the set of the vertices at distance at most $r$ from $v$. Therefore, the statement of the BNC can be reformulated as the fact that the vertex set of any graph on $n$ vertices can be covered by balls of radius $0, 1, ..., \lceil \sqrt{n} \rceil - 1$. One can therefore wonder now which sets of radii are enough to cover any $n$ vertex graph.

A graph $G$ is $\mathcal{R}$-burnable for some finite set of $\mathcal{R} = \{r_1, ..., r_p\} \subseteq \mathbb{N}$ if there exist vertices $v_1, ..., v_p$ of $G$ such that $\cup_{i \in \{1, ..., p\}} B(v_i, r_i) = V(G)$. Note that multisets are not eligible, which is crucial in later arguments. As referenced earlier, the BNC states that every graph on $n$ vertices is $\{0, 1, ..., \lceil \sqrt{n} \rceil - 1\}$-burnable. We propose the stronger following conjecture.

**Conjecture 7.** Let $T$ be a tree of growth $k$ and of order $n$. If $\mathcal{R}$ is a finite set of integers such that $\{0, 1, ..., k\} \subseteq \mathcal{R}$ and $\sum_{r \in \mathcal{R}} (2r + 1) \ge n$, then $T$ is $\mathcal{R}$-burnable.
The intuition behind this conjecture comes from the idea that for a path, supposedly one of the worst example for the burning number, the ball of radius $r$ covers at most $2r+1$ vertices. Therefore, radii in $\mathcal{R}$ would cover $\sum_{r \in \mathcal{R}} (2r+1)$ vertices. Moreover, observe that

$$ \sum_{r=0}^{\lfloor \sqrt{n} \rfloor - 1} (2r + 1) = \lfloor \sqrt{n} \rfloor^2 \geq n, $$

thus Conjecture 7 is stronger than the BNC.

The article is organized as follows. In Section 2, we prove Theorem 1 and its two corollaries Theorem 2 and Theorem 3. In Section 3, we prove Theorem 6. The concluding section describes further directions.

All graphs we consider are simple, finite, and undirected. The distance between vertices $u$ and $v$ is denoted by $d(u, v)$. The diameter of a graph $G$ is denoted by $diam(G)$. For a vertex $v$ and an integer $r$, we denote by $B(v, r)$ the ball of radius $r$ centered on $v$; that is, the set of vertices at distance at most $r$ from $v$. We will use the notation $\text{radius}(G)$ for the radius of a graph, that is the smallest integer $r$ such that there exists a vertex $x$ of $G$ with $V(G) = B(x, r)$. For background on graph theory, see [Wes01].

# 2 General bounds

## 2.1 Improved upper bound on the burning number

The goal of this section is to prove Theorem 1. The proof relies heavily on the following lemma.

**Lemma 8.** For every tree $T$ and nonempty and finite $\mathcal{R} \subseteq \mathbb{N}$, there exists $r \in \mathcal{R}$ such that either $\text{radius}(T) \leq r$ or there exists a subtree $T'$ of $T$ such that

1. $T \setminus T'$ is connected,

2. $\text{radius}(T') \leq r$, and

3. $|V(T')| \geq r + |\mathcal{R}|/2$.

We first show how to quickly derive Theorem 1 assuming that the lemma holds.

*Proof of Theorem 1.* Given a tree $T$ on $n$ vertices and an integer $p$, we repeatedly apply Lemma 8 to obtain that $T$ is $\{0, 1, \dots, p\}$-burnable unless

$$ n > \sum_{i=0}^{p} i + \sum_{i=0}^{p} i/2 = \frac{3p(p+1)}{4}. $$

We therefore have that $p \leq \lfloor \sqrt{\frac{4}{3}n} \rfloor + 1$, as desired. $\square$

<figure><img src="image_2.png" /></figure>
Proof of Lemma 8. Let $T$ be a tree and $\mathcal{R} \subseteq \mathbb{N}$ satisfying its hypotheses. We consider a maximum length path $P = (t_0, t_1, \dots, t_\ell)$ of $T$, and root $T$ in $t_\ell$. For $0 \le i \le \ell$, we define $T_i$ to be the subtree of $T$ rooted in $t_i$, containing all descendants of $t_i$ including itself. For $0 \le i \le \ell$, we also define:

$$ \phi(i) = \max\{j: T_j \subseteq B(t_i, i)\}. $$

It is straightforward to notice that $i \le \phi(i) \le 2i$. Further, if $\phi(r) = \ell$ for some $r$, then $T = T_\ell \subseteq B(t_r, r)$ so we have the first possible outcome of the lemma. We therefore assume from now on that $\phi(r) < \ell$ for every $r \in \mathcal{R}$. For any $r \in \mathcal{R}$, note that the tree $T' = T_{\phi(r)}$ satisfies the two first conditions required by the second outcome of the lemma, so we may also assume that for any $r \in \mathcal{R}$, $T_{\phi(r)}$ contains strictly less than $r + |\mathcal{R}|/2$ vertices. In particular, since vertices $t_0, t_1, \dots, t_{\phi(r)}$ belong to $T_{\phi(r)}$, we have that $\phi(r) < r + |\mathcal{R}|/2 - 1$ for every $r \in \mathcal{R}$.

Let $\mathcal{R}'$ be the set of the $N = \lceil |\mathcal{R}|/2 \rceil$ largest elements of $\mathcal{R}$ and $r \in \mathcal{R}'$. A straightforward but crucial consequence of the fact that $\mathcal{R}$ is not a multiset is that $r \ge |\mathcal{R}| - N \ge |\mathcal{R}|/2 - 1$ and hence $\phi(r) < 2r$. Further, by the definition of $\phi(r)$ and since $\phi(r) < \ell$, there exists a vertex $x_r \in T_{\phi(r)+1} \setminus T_{\phi(r)}$ such that $d(t_r, x_r) = r + 1$. The inequality $\phi(r) < 2r$ implies that $x_r$ lies outside $P$ and we observe that because of the distance condition, $x_r \ne x'_r$ for distinct $r$ and $r'$ in $\mathcal{R}'$. Note that $\phi(r_i) > \phi(r_j)$ implies that $x_{r_j} \in T_{\phi(r_i)}$.

Denote by $r_1 < r_2 < \dots < r_N$ the elements of $\mathcal{R}'$, and let $m$ the smallest index such that $\phi(r_m) \ge \phi(r_N)$. By the preceding discussion, $T_{\phi(r_m)}$ contains all vertices $x_{r_i}$ for every $i < m$ and contains also at least $r_N + 1$ vertices from $P$. Hence, it has order at least

$$ m + r_N \ge m + r_m + (N - m) = r_m + N \ge r_m + |\mathcal{R}|/2 $$

since the $r_i$ are distinct integers, which yields the result. $\square$

## 2.2 Graphs of minimum degree 3 and 4

Using Theorem 1, we are now ready to argue that the BNC almost holds for graphs of minimum degree at least 3, and obtain Theorems 2 and 3. We use the following two convenient theorems.

**Theorem 9.** [KW91] Every connected graph on $n$ vertices each of degree at least 3 admits a spanning tree with at least $\frac{n}{4} + 2$ leaves.

**Theorem 10.** [GW92] Every connected graph on $n$ vertices each of degree at least 4 admits a spanning tree with at least $\frac{2n+8}{5}$ leaves.

Proof of Theorem 2. Let $G$ be a connected graph on $n$ vertices each of degree at least 3. By Theorem 9, there is a spanning tree $T$ with at least $\frac{n}{4} + 2$ leaves. Let $T'$ be the tree obtained from $T$ by deleting all leaves. Note that $b(T) \le b(T') + 1$. By Theorem 1, we have that

$$ b(T') \le \left\lceil \sqrt{\frac{4}{3}} \cdot \left( \frac{3}{4}n - 2 \right) \right\rceil + 1. $$

$$ \text{We derive that } b(G) \le b(T) \le \lceil \sqrt{n} \rceil + 2. \quad \square $$
*Proof of Theorem 3.* Let $G$ be a connected graph on $n$ vertices each of degree at least 4. By Theorem 10, there is a spanning tree $T$ with at least $\frac{2n+8}{5}$ leaves. Let $T'$ be the tree obtained from $T$ by deleting all leaves. Note that $b(T) \le b(T') + 1$. By Theorem 1, we have that

$$b(T') \le \left\lceil \sqrt{\frac{4}{3}} \cdot \left( \frac{3n-8}{5} \right) \right\rceil + 1.$$

We derive that $b(G) \le b(T) \le \lceil \sqrt{n} \rceil$ when $n$ is large enough (for example, if $n \ge 325$). $\square$

# 3 Caterpillars Result

This section is devoted to the proof of Theorem 4. We start with another inductive result similar to Lemma 8, that will be of use in the final step of the proof.

## 3.1 Inductive Lemmas

**Lemma 11.** For every $k$-caterpillar $T$ and any integer $r$, either $\text{radius}(T) \le r$ or there exists a subtree $T'$ of $T$ such that

1. $T \setminus T'$ is connected,

2. $\text{radius}(T') \le r$, and

3. $|V(T')| \ge 2r + 1 - k$.

*Proof.* The proof is based on an analogous argument as the one of Lemma 8: we consider a maximum length path $P = (t_0, t_1, \dots, t_\ell)$ of $T$, we consider $T$ to be rooted in $t_\ell$, and define $T_i$ to be the subtree rooted in $t_i$. We also define $\phi(r)$ to be the maximum $i$ such that $T_i$ is contained in $B(t_r, r)$. Either $\phi(r) = 2r + 1$, or there exists a vertex $v \notin P$ such that

1. The closest vertex from $v$ on $P$ is $t_{\phi(r)+1}$, and

2. $d(t_{\phi(r)+1}, v) = 2r - \phi(r)$.

Since $T$ is a $k$-caterpillar and $P$ a maximum path, every vertex is at distance at most $k$ from $P$, and so $2r - \phi(r) \le k$. The latter inequality implies the desired result since $T_{\phi(r)}$ contains at least the vertices $t_0, t_1, \dots, t_{\phi(r)}$. $\square$

By applying repeatedly the previous lemma radius by radius we obtain the following result for $k$-caterpillars.

**Corollary 12.** Let $T$ be a tree of growth $k$ and of order $n$. If $\mathcal{R}$ is a set of integers such that $\sum_{r \in \mathcal{R}} (2r + 1 - k) \ge n$, then $T$ is $\mathcal{R}$-burnable.
Before starting the proof of the theorem, we state a final inductive lemma. The goal of this lemma is to burn a large part of the caterpillar with the ball of maximum radius. This part can either be a long path where all vertices attached are close to the path ($d(u, v)$ large and $k$ small in the following statement) or the opposite, that is, a short path with some vertices quite far away from the path ($d(u, v)$ small and $k$ large).

**Lemma 13.** Let $\mathcal{R}$ be a finite set of integers and denote by $\mathcal{R}$ its maximum element. Let $T$ be a tree and $P$ a path in $T$ with two endpoints $u$ and $v$. Denote by $T_u$ (respectively, $T_v$) the connected component of $T \setminus (P \setminus \{u, v\})$ containing $u$ (respectively, $v$), and define $k = \max_{x \notin V(T_u \cup T_v)} d(P, x)$. If $T_u \cup T_v + uv$ is $(\mathcal{R} \setminus \{R\})$-burnable and $d(u, v) \le 2R - 2k + 2$, then $T$ is $\mathcal{R}$-burnable.

*Proof.* Define $\mathcal{R}' = \mathcal{R} \setminus \{R\}$, $T' = (T_u \cup T_v + uv)$ and $T_P = T \setminus (T_u \cup T_v)$. By hypothesis, $T'$ is $\mathcal{R}'$-burnable so let us consider a set of vertices $(x_r)_{r \in \mathcal{R}'}$ such that the balls $B_{T'}(x_r, r)_{r \in \mathcal{R}'}$ cover $T'$. We want to keep in $T$ the same balls centered in the same vertices and add a ball of radius $R$ that covers every vertex not covered by those balls. Since $T$ is a tree, it is sufficient to show that no two non-covered vertices are at distance more than $2R$ (centering the ball at the middle of a longest path in $T$ between non-covered vertices covers all of them).

Define $W = V(T) \setminus \cup_{r \in \mathcal{R}'} B_T(x_r, r)$ and assume for a contradiction that there exists $(x, y) \in W^2$ such that $d_T(x, y) > 2R$. We first define $\mathcal{R}_u = \{r \in \mathcal{R}': x_r \in T_u\}$, similarly $\mathcal{R}_v = \mathcal{R}' \setminus \mathcal{R}_u$, and:

$$r_v = \max_{r \in \mathcal{R}_v} (r - d_T(x_r, v)) \quad \text{and} \quad r_u = \max_{r \in \mathcal{R}_u} (r - d_T(x_r, u)).$$

It is evident that $\max(r_u, r_v) < R$ and observe also that any vertex $w$ in $W$ satisfies $d(w, u) > r_u$ and $d(w, v) > r_v$. Therefore, if $z \in T_u \cap W$, we derive that $r_u < d(z, u) < r_v$. Hence, $r_u < r_v$ and so $T_u \cap W$ or $T_v \cap W$ is empty.

Without loss of generality, assume that $r_u \le r_v$, so that $T_v \cap W = \emptyset$. In particular, neither $x$ nor $y$ can belong to $T_v$. Moreover, for any $w \in W \cap T_P$, observe that

$$d(w, u) + r_v < d(w, u) + d(w, v) = d(u, v) + 2d(w, P) \le 2R + 2.$$

We are now able to derive a contradiction in every possible case:

1. If $(x, y) \in T_P^2$, then $d(x, y) \le d(x, P) + d(y, P) + d(u, v) - 2 \le 2R$.

2. If $(x, y) \in T_u^2$, then $d(x, y) \le d(x, u) + d(y, u) \le 2r_v < 2R$.

3. If $(x, y) \in T_u \times T_P$, then $d(x, y) = d(x, u) + d(y, u) < r_v + d(y, u) < 2R + 2$.

The proof follows. $\square$

<figure><img src="image_3.png" /></figure>
## 3.2 Proof of Theorem 6

Let $k$ and $c$ be integers, and define $f(k) = 4k^2 + 5k - 2$. If Theorem 6 is false, then there exists a $k$-caterpillar $T$ such that $b(T) > \lceil \sqrt{|V(T)| + c} \rceil > f(k)$, so let us assume now that $T$ is a minimum order such $k$-caterpillar.

To simplify notation, we will in the following denote $n = |V(T)|$, $R = \lceil \sqrt{n+c} \rceil - 1$ and $\mathcal{R}$ the set of integers $\{0, 1, \dots, R\}$, so that $T$ is not $\mathcal{R}$-burnable and $R \ge f(k)$.

Here is a simple claim on $T$ that we will use often.

**Claim 14.** There is no integer $R' < R$ and subtree $T'$ of $T$ such that $T \setminus T'$ is covered by balls with radii between $R'$ and $R$ such that $|V(T) \setminus V(T')| \ge \sum_{r=R'}^{R}(2r+1)$.

*Proof.* Since $|V(T)| + c \le \sum_{r=0}^{R}(2r+1)$, we have that

$$|V(T')| + c \le \sum_{r=0}^{R'-1} (2r+1).$$

Therefore, $T'$ would be a smaller order counterexample contradicting the minimality of $T$. □

We now consider a spine $S$ of $T$; that is, a path of maximum length, so that every vertex not in the path is at distance at most $k$ from the path. We arbitrarily choose $s_0$ to be one endpoint of $S$, and for two vertices $s'$ and $s''$ of $S$, we write $s' < s''$ if $d(s_0, s') < d(s_0, s'')$. In particular, $s'$ and $s''$ are distinct.

Let us denote by $\mathcal{R}_1 = \{r \in \mathcal{R}, (R+k)/2 < r \le R\}$. We now define the main object in our approach. A sequence of pairs $(c_i, r_i) \in V(S) \times \mathcal{R}_1$ for $1 \le i \le t$ is *admissible* if

1. For all $i < j$, $r_i \ne r_j$,

2. For all $i$, $c_i < c_{i+1}$ and $d(c_i, c_{i+1}) = r_i + r_{i+1} + 1$,

3. For all $i$, $V_i = V \setminus (\cup_{j \le i} B(c_j, r_j))$ induces a connected subtree $T_i$ of $T$, and

4. For all $i$, $S \cap V_i$ is a spine of $T_i$.

Phrased differently, we pack balls along the spine without disconnecting the tree nor changing the spine.

**Claim 15.** Let $C$ be an admissible sequence $(c_i, r_i)$ for $1 \le i \le t$ such that the sequence of radii $(r_1, r_2, \dots, r_t)$ is lexicographically maximal. We then have that

1. $t > |\mathcal{R}_1| - 2k$, and

2. $|\cup_{i=1}^t B(c_i, r_i)| \ge \sum_{i=1}^t (2r_i + 1) + 2k^2$.
Note that the maximality condition implies that this maximal sequence may obtained
by a process where at each step, we chose the largest remaining radii that keeps the se-
quence admissible.

Let us prove first that this claim implies our result. Let $T'$ the subtree induced by
$V \setminus \bigcup_{i=1}^t B(c_i, r_i)$. Since $\mathcal{R}' = \mathcal{R}_1 \setminus \{r_i \in \mathcal{R}_1, 1 \le i \le t\}$ contains less than $2k$ elements by the
first item of the claim, we can apply $2k$ times Lemma 11 to obtain a subtree $T''$ such that
$T' \setminus T''$ is covered by balls with radius in $\mathcal{R}'$ and $|V(T') \setminus V(T'')| \ge \sum_{r \in \mathcal{R}'} (2r + 1) - 2k^2$.
Overall, $T \setminus T''$ is coverable by balls of radius in $\mathcal{R}_1$ and $|V(T) \setminus V(T'')| \ge \sum_{r \in \mathcal{R}_1} (2r + 1)$,
which is impossible by Claim 14.

*Proof of Claim 15.* Consider $\mathcal{C}$ as in the statement and fix some integer $j \le t$. Denote
$V' = V \setminus \bigcup_{i \le j} B(c_i, r_i)$. Note that $T' = T[V']$ is a $k$-caterpillar, and that by assumption
$S' = S \cap V'$ is a spine of $T'$. Let $s_0' < s_1' < \dots < s_p'$ the vertices of $S'$. For a vertex $v$ not
in the spine, we will say that $v$ is *pending to* $s_i'$ if $s_i'$ is the closest vertex to $v$ on the spine.
Let $\mathcal{R}' = \mathcal{R}_1 \setminus \{r_i \in \mathcal{R}_1, 1 \le i \le j\}$. Now by maximality of $\mathcal{C}$ we have that if $r \in \mathcal{R}'$, then:

1. Either $j < t$ and $r \le r_{j+1}$, or

2. The removal of $B(s'_r, r)$ disconnects $T'$, or

3. The vertices $s'_{2r+1}, s'_{2r+2}, \dots, s'_p$ are no longer a spine of $T' \setminus B(s_r, r)$.

If $j = t$ or $r > r_{j+1}$, then this implies that there is a vertex $v_r \notin S'$ such that:

1. Either $v_r$ is in the subtree pending to $s'_i$ for some $2r-k \le i \le 2r$ and $d(s'_0, v_r) = 2r+1$,
as $v_r$ is not covering it, or

2. The vertex $v_r$ is in the subtree pending to $s'_i$ for some $2r < i \le 2r+k$ and $d(s'_0, v_r) = 2i - 2r$, as the distance from $s'_i$ to that node must be 1 plus the distance to the last node covered by $s'_{2r+1}$.

We want to prove that all such $v_r$ are distinct. Let us say that $v_r$ is *type 1* of it corresponds to the first case above, and of *type 2*, otherwise. See Figure 3.1 for representation of the two possibilities.

The distance to $s_0'$ condition implies that elements of type 1 are pairwise distinct, and
same for elements of type 2. We conclude that the parity of this distance is odd in one
case and even in the other, which also forbids an element of type 1 to be equal to an
element of type 2.

If $j=t$, then this implies that we have at least $|\mathcal{R}'|$ vertices outside the spine such that
each of them are pending to some $s'_i$ for $i$ between $\min\{2r-k, r \in \mathcal{R}'\} \ge 3k$ (remember all
elements in $\mathcal{R}_1$ are at least $(R+k)/2 \ge 2k$) and $\max\{2r+k, r \in \mathcal{R}'\} \le 2R+k$. We now
use Lemma 13 applied to $u = s'_{3k-1}$ and $v = s'_{2R+k+1}$. We have that $d(u,v) = 2R-2k+2$
and since $T$ is not $\mathcal{R}$-burnable, the tree $T'$ denoted $T_u + T_v + uv$ in the statement of
the lemma should not be $\mathcal{R} \setminus \{R\}$-burnable. By the minimality of $T$, this implies that
<figure><img src="image_4.png" /><figcaption>Figure 3.1: Vertices of type 1 and 2.</figcaption></figure>

$T \setminus T'$ contains at most $2R$ elements, which in turn implies that $\mathcal{R}'$ contains less than $2k$ elements, which is exactly the first item of the claim.

If $j < t - 1$, then we denote by $\mathcal{R}''$ the set $\{r \in \mathcal{R}', r > r_{j+1}\}$. When $\mathcal{R}''$ is not empty, we denote by $r''$ the largest element of $\mathcal{R}'$. The discussion above implies that there are at least $|\mathcal{R}''|$ vertices outside the spine that are pending between $s'_{2r_{j+1}-k}$ and $s'_{2r''+1+k}$. By the definition of $\mathcal{R}_1 = \{r \in \mathcal{R}, (R+k)/2 < r \le R\}$, we have that

$$2r'' + 1 + k \le 2R + k + 1 < 2r_{j+1} + 2r_{j+2} + 1 - k,$$

implying that all those vertices outside the spine will be included into either $B(c_{j+1}, r_{j+1})$ or $B(c_{j+2}, r_{j+2})$. In fact, they cannot be included in $B(c_{j+1}, r_{j+1})$ as for any $r \in \mathcal{R}'$, $d(s'_0, v_r) = 2r + 1 > 2r_{j+1} + 1$, therefore they are only included in $B(c_{j+2}, r_{j+2})$ and are not counted twice.

The total number of vertices outside the spine that will be included into the union of the balls in our sequence is at least the number of times balls in $\mathcal{R}_1$ are rejected for a smaller ball in the process. We claim that this number is at least $R - \min_{i \le t} r_i$.

We let $m_j = \min_{i \le j} r_i$ and observe first that at any time of the process, $\{r_i, 1 \le i \le j\}$ is never equal to the interval $[m_j, R]$ by Claim 14. Hence, there is at least one radius of size greater that $m_j$ that has been rejected. Now consider each step $j$ where we pick a new minimum, that is $m_j = r_j$. We have rejected at least $m_{j-1} - m_j$ radii (at least 1 greater than $m_{j-1}$ and $m_{j-1} - m_j - 1$ between $m_j$ and $m_{j-1}$). Overall, this gives that the number of total rejections is at least $R - m_t$ as claimed and this concludes the proof since

$$R - m_t \ge t \ge |\mathcal{R}_1| - 2k + 1 \ge (R - k)/2 - 2k + 1 \ge 2k^2,$$

where the last inequality comes from the assumption $R \ge f(k)$. $\square$

# 4 Conclusion and Further Directions

We provided the best known upper bound for the burning number of a connected graphs, and have shown that the burning graph conjecture is asymptotically true for $k$-caterpillars. We can in fact prove that this extends to Conjecture 7 with analogous arguments, though we do not go into details. In this case, we can also do a finer analysis to modify the bound
in Theorem 6 from $O(k^4)$ to $O(k^2)$, though it did not seem to us enough to justify an additional few pages of proofs.

The two proofs of Theorem 1 and Theorem 6 may seem similar in approach: in both cases, we consider a maximum order path and try to place large balls centered on the path in a greedy fashion. However, the induction makes a big difference: in the case of Theorem 6, we pick a maximum path initially and all balls chosen will be centered on the path, whereas in the proof of Theorem 1, at each step we take a new maximum path before removing a ball centered on it, so that in the next step, the new maximum path might not be a subpath of the previous one. In this proof, the set of centers constructed may not lie on a common path. One might wonder if the BNC could be true with the additional requirement that all balls are centered along some path. This is not the case, as can be seen by considering the graph obtained from a star with $p$ leaves by subdividing each edge $p$ times.

Theorem 4 states that, for a fixed value of $k$, there are a finite number of graphs that could be counterexample of the BNC. As it is now, the statement induces a large number of cases, it would be interesting to reduce this number enough to obtain a computer-based proof of the BNC for small values of $k$.

# Addendum

Since the publication and advertisement of the present contribution, Norin and Turcotte solved The Burning Number Conjecture asymptotically [NT22], using radically new ideas.

# References

[BBJ$^{+}$18] Stéphane Bessy, Anthony Bonato, Jeannette Janssen, Dieter Rautenbach, and Elham Roshanbin. Bounds on the burning number. *Discrete Applied Mathematics*, 235:16–22, 2018.

[BJR14] Anthony Bonato, Jeannette Janssen, and Elham Roshanbin. Burning a graph as a model of social contagion. In *International Workshop on Algorithms and Models for the Web-Graph*, pages 13–22. Springer, 2014.

[BJR16] Anthony Bonato, Jeannette Janssen, and Elham Roshanbin. How to burn a graph. *Internet Mathematics*, 12(1-2):85–100, 2016.

[BL19] Anthony Bonato and Thomas Lidbetter. Bounds on the burning numbers of spiders and path-forests. *Theoretical Computer Science*, 794:12–19, 2019.

[Bon21] Anthony Bonato. A survey of graph burning. *Contributions to Discrete Mathematics*, 16:185–197, 2021.

[GW92] Jerrold R. Griggs and Mingshen Wu. Spanning trees in graphs of minimum degree 4 or 5. *Discrete Mathematics*, 104:167–183, 1992.
[HTK19] Michaela Hiller, Eberhard Triesch, and Arie MCA Koster. On the burning number of *p*-caterpillars. *AIRO Springer Ser.*, 5, Springer, Cham, 2021, 145–156.

[KMZ20] Shahin Kamali, Avery Miller, and Kenny Zhang. Burning two worlds: algorithms for burning dense and tree-like graphs. In *International Conference on Current Trends in Theory and Practice of Informatics*, pages 113–124. Springer, 2020.

[KW91] Daniel J Kleitman and Douglas B West. Spanning trees with many leaves. *SIAM Journal on Discrete Mathematics*, 4(1):99–106, 1991.

[LHH20] Huiqing Liu, Xuejiao Hu, and Xiolan Hu. Burning number of caterpillars. *Discrete Applied Mathematics*, 284:332–340, 2020.

[LL16] Max Land and Linyuan Lu. An upper bound on the burning number of graphs. In *Workshop on Algorithms and Models for the Web-Graph*, pages 1–8. Springer, 2016.

[NT22] Sergey Norin and Jérémie Turcotte. The burning number conjecture holds asymptotically. arXiv:2207.04035, 2022.

[Ros16] Elham Roshanbin. *Burning a graph as a model of social contagion*. PhD thesis, 2016.

[Wes01] Douglas B. West. *Introduction to Graph Theory*, 2nd edition. Prentice Hall, 2001.