On the Burning Number of p-Caterpillars

Abstract

The burning number is a recently introduced graph parameter indicating the spreading speed of content in a graph through its edges. While the conjectured upper bound on the necessary number of time steps until all vertices are reached is proven for some specific graph classes, it remains open for trees in general. We present two different proofs for ordinary caterpillars and prove the conjecture for a generalised version of caterpillars and for trees with a sufficient number of legs. Furthermore, determining the burning number for spider graphs, trees with maximum degree three and path-forests is known to be $\mathcal {N}\mathcal {P}$-complete; however, we show that the complexity is already inherent in caterpillars with maximum degree three.

1 Introduction

Given an undirected graph G = (V, E), the burning number b(G) indicates the minimum number of steps to inflame the whole graph while in each time step the fire spreads from all burning vertices to their neighbours and one additional vertex can be lit. This concept was introduced as a possible representation of the spread of content in an online social network in [2], but also other issues, e.g. the contagion of illnesses, can be modelled.

A sequence of vertices B = (b ₁, …, b _m) is said to be a burning sequence or burning strategy if the vertices burn off the whole graph in m steps when lit successively. For m = b(G), we say B is an optimum burning sequence or an optimum burning strategy. The set of all vertices which receive the fire from a vertex b _i (or theoretically would, if they were not already burning) together with b _i itself is called a burning circle and is denoted by V _i. Thus, the problem of finding a burning strategy can be reformulated into a covering problem V = V ₁ ∪⋯ ∪ V _m. The extent of a burning circle is given by $\operatorname {\mathrm {diam}}(V_i)+1=2i-1$. We denote the problem of determining the burning number for a graph by Burning Number.

In 2014, an upper bound for the burning number was conjectured for all connected graphs [2].

Burning Number Conjecture

If G is a connected graph of order n, then

$$\displaystyle \begin{aligned} b(G)\leq \left\lceil\sqrt{n}\right\rceil. \end{aligned}$$

The conjecture is proven for paths, cycles, Hamiltonian graphs and spiders [3]. Further, it can be easily checked that graphs with a small vertex number fulfil the conjecture. For paths whose length is a square number, the conjecture holds with equality and, as shown in [2], the conjecture is true for all connected graphs if it holds for trees in general.

Firstly, in Sect. 2 the Burning Number Conjecture is proven for caterpillars in two different ways: once by using the principle of infinite descent and alternatively, by determining a burning strategy complying with the conjectured bound. Subsequently, in Sect. 3, we show that Burning Number is $\mathcal {N}\mathcal {P}$-complete for caterpillars. In Sect. 4, we focus on the validity of the conjecture for 2-caterpillars and p-caterpillars with a sufficient number of leaves relative to the order of the graph.

2 The Burning Number Conjecture for Caterpillars

In this section, we investigate the Burning Number Conjecture for caterpillars, trees in which all vertices are within the distance one of a central spine or more vivid:

A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed. [4]

Consequently, the graph class of caterpillars can also be described by forbidden minors C ₃ and S _2,2,2 as in Fig. 1.

Fig. 1

Forbidden minors C ₃ and S _2,2,2 in a caterpillar

Let G = (V, E) denote a caterpillar with n := |V | vertices, a spine P _ℓ = {v ₁, …, v _ℓ} of length ℓ and n − ℓ vertices adjacent to P _ℓ ∖{v ₁, v _ℓ}, which we call legs. We assume ℓ ≥ 4 and n ≥ ℓ + 2; otherwise G is a spider graph and the conjecture holds. Further, it can easily be seen that the conjecture is true for all graphs with n ≤ 9.

Applying the (proven) conjecture for paths to the Spine P _ℓ, we clearly get the following upper bound for the caterpillar.

Proposition 1

If G is a caterpillar, then $b(G)\leq \left \lceil \sqrt {\ell }\right \rceil +1$ . Thus, the conjecture is proven to be true for $\left \lceil \sqrt {n}\right \rceil \geq \left \lceil \sqrt {\ell }\right \rceil +1$.

In fact, the conjecture holds for all caterpillars, which can be shown using the principle of infinite descent.

Theorem 1 (Burning Number Conjecture for Caterpillars)

The burning number of a caterpillar G satisfies $b(G)\leq \left \lceil \sqrt {n}\right \rceil$.

Proof

Let the graph G be a caterpillar and a minimum counterexample regarding n with $b(G) > \left \lceil \sqrt {n}\right \rceil =: k$. We distinguish two cases:

• If either the spine vertex v _2k−1 has no legs or v _2k−1 has a leg, but at least one of the vertices v ₁, …, v _2k−2 has an adjacent leg as well, we remove the largest burning circle V ₁ with extent $\operatorname {\mathrm {diam}}(V_1)+1=2k-1$ without loss of generality at the end of the spine P _l as shown in Fig. 2. Depending on whether v _2k−1 is legless or not, we shorten the spine by 2k − 1 or (2k − 1) − 1 vertices, respectively, to maintain the connectivity.

  Fig. 2

  

  In the proof of Theorem 1, we generate G ^′ by removing the grey vertices of V ₁ in the minimum counterexample G

  In both sub-cases, we obtain a new caterpillar G ^′ with

  

  and for the burning number of G ^′ it follows that $b(G^\prime ) > \left \lceil \sqrt {n}\right \rceil -1$; otherwise G would not be a counterexample. Since G is minimum by assumption, we further have $b(G^\prime ) \leq \left \lceil \sqrt {n^\prime }\right \rceil$. This yields

  

  and thus $\left \lceil \sqrt {n^\prime }\right \rceil = \left \lceil \sqrt {n}\right \rceil$. With the estimate from above $\left \lceil \sqrt {n-2\left \lceil \sqrt {n}\right \rceil +1}\right \rceil =\left \lceil \sqrt {n}\right \rceil$, and therefore the two radicands lie between the same square numbers $\left \lceil \sqrt {n}\right \rceil ^2$ and $\left (\left \lceil \sqrt {n}\right \rceil -1\right )^2$. As a consequence,

  $$\displaystyle \begin{aligned} n-\left(\left\lceil\sqrt{n}\right\rceil-1\right)^2 &\; \geq\; 2\left\lceil\sqrt{n}\right\rceil-1+1, \end{aligned} $$

  or equivalently, $n \geq \left (\left \lceil \sqrt {n}\right \rceil -1\right )^2+2\left \lceil \sqrt {n}\right \rceil = \left \lceil \sqrt {n}\right \rceil ^2+1$. This is a contradiction.

• If otherwise v ₁, …, v _2k−2 are legless, but v _2k−1 is not, we remove the two largest burning circles V ₁ with extent $\operatorname {\mathrm {diam}}(V_1)+1=2k-1$ and V ₂ with extent $\operatorname {\mathrm {diam}}(V_2)+1=2k-3$ without loss of generality at the end of the spine P _ℓ. We shorten the spine by (2k − 3) + (2k − 1) − 1 vertices as shown in Fig. 3.

  Fig. 3

  

  Let v _2k−1 have adjacent legs and v ₁, …, v _2k−2 be legless. We remove the grey vertices

  Analogously to the first case, for the remaining caterpillar G ^′′ it follows that

  $$\displaystyle \begin{aligned} \ell^{\prime\prime} &\leq \ell-(2k-3)-(2k-1)+2 ,\\ n^{\prime\prime} &\leq n-(2k-3)-(2k-1)+1-1 \leq \left( \left\lceil\sqrt{n}\right\rceil-2\right)^2 , \end{aligned} $$

  and $b(G^{\prime \prime }) > \left \lceil \sqrt {n}\right \rceil -2$; otherwise, G would not be a counterexample. Since G is minimum, we further have $b(G^\prime ) \leq \left \lceil \sqrt {n^{\prime \prime }}\right \rceil$. This yields the contradiction

  $$\displaystyle \begin{aligned}\left\lceil\sqrt{n}\right\rceil-2 \;< \;b(G^{\prime\prime})\;\leq\; \left\lceil\sqrt{n^{\prime\prime}}\right\rceil \;\leq \;\left\lceil\sqrt{n}\right\rceil-2. \end{aligned}$$

Therefore, the minimum counterexample cannot exist. □

The following alternative proof works without the principle of infinite descent and provides a burning strategy in $\left \lceil \sqrt {n}\right \rceil$ steps for all caterpillars.

Proof

Let again $k:=\left \lceil \sqrt {n}\right \rceil$ denote the maximum number of steps such that the conjecture still holds. Recursively removing burning circles to reduce the vertex number at least down to the next smaller square number, we consider two cases:

• In the first case, v _2k−1 ∈ P _ℓ has no legs. After deleting v ₁, …, v _2k−1 with all adjacent legs, the remaining graph has at most $n-(2k-1)\leq \left \lceil \sqrt {n}\right \rceil ^2-2\left \lceil \sqrt {n}\right \rceil +1=(\left \lceil \sqrt {n}\right \rceil -1)^2$ vertices as depicted in Fig. 4.

  Fig. 4

  

  In the first case, v _2k−1 is legless and we delete the grey vertices

• In the other case, we distinguish whether any of the vertices v ₁, …, v _2k−2 has an adjacent leg or not. If not all of these spine vertices are legless, we remove v ₁, …, v _2k−2 together with their legs as outlined in Fig. 5. Again, the vertex set of the remaining graph contains—just as in the first case—at most $(\left \lceil \sqrt {n}\right \rceil -1)^2$ vertices.

  Fig. 5

  

  We assume v _2k−1 and at least one of v ₁, …, v _2k−2 to have legs and delete the grey vertices

  Otherwise, if v ₁, …, v _2k−2 are legless and v _2k−1 has an adjacent leg as shwon in Fig. 3, we delete v ₁, …, v _2k−3 and further v _(2k−3)+1, …, v _{(2k−3)+(2k−2)} with all their legs (at least the leg adjacent to v _2k−1) such that the new graph consists of at most $n-(2k-3)-(2k-2)-1\leq \left \lceil \sqrt {n}\right \rceil ^2-(2\left \lceil \sqrt {n}\right \rceil -1)-(2\left \lceil \sqrt {n}\right \rceil -3)=(\left \lceil \sqrt {n}\right \rceil -2)^2$ vertices.

Hence, after the vertex removal the order of the remaining graph G ^′ decreases at least to $n^\prime \leq (\left \lceil \sqrt {n}\right \rceil -1)^2$ and the claim follows recursively. □

It can easily be seen that the alternative proof yields an algorithm to burn a caterpillar in $\left \lceil \sqrt {n}\right \rceil$ steps, though may not necessarily be optimum.

3 The $\mathcal {N}\mathcal {P}$-Completeness of the Burning Number Problem for Caterpillars

The $\mathcal {N}\mathcal {P}$-completeness of determining the burning number for caterpillars indicates the unstructured nature of the problem as the difficulty or complexity is already hidden in such a simple graph class. Our proof is structured similar to the proof for trees of maximum degree three in [1] and uses a reduction from Distinct 3-Partition.

Problem: :

Distinct 3-Partition

Instance: :

A set X = {a ₁, …, a _3n} of 3n distinct positive integers and a positive integer S, fulfilling $\sum _{i=1}^{3n}a_i=n\cdot S$ with $\frac {S}{4}<a_i<\frac {S}{2}$ for all 1 ≤ i ≤ 3n.

Question: :

Can X be partitioned into n triples each of whose elements sum up to S?

Distinct 3-Partition is $\mathcal {N}\mathcal {P}$-complete in the strong sense as shown in [5], which means the problem remains $\mathcal {N}\mathcal {P}$-complete even if S is bounded from above by a polynomial in n.

Theorem 2

Burning Number is $\mathcal {N}\mathcal {P}$ -complete for caterpillars of maximum degree three.

Proof

Burning Number is in $\mathcal {N}\mathcal {P}$ as a burning sequence for a graph can be verified in polynomial time by checking whether the whole vertex set is covered by the union of the corresponding burning circles.

To prove the $\mathcal {N}\mathcal {P}$-completeness, we reduce Distinct 3-Partition in polynomial time to Burning Number. Given an instance for Distinct 3-Partition as stated above, we denote $m:=\max \{a_i~|~a_i\in X\}$, $\underline {m}:=\{1,\dots,m\}$ and $Y:= \underline {m}\setminus X$. Transferred to the universe of Burning Number, we get X′ := {2a _i − 1 | a _i ∈ X}, S′ := 2S − 3, $\mathcal {O}_m:=\{2i-1~|~i\in \underline {m}\}$ and $Y':=\mathcal {O}_m\setminus X'$.

Now we construct a caterpillar G of maximum degree three as follows: For each triple whose unknown elements should add up to S we build a path $Q^{X'}_i$ (for all 1 ≤ i ≤ n) of order S′ and for all numbers in Y  (which are not available for the triples) a separate path $Q^{Y'}_i$ (for all 1 ≤ i ≤ m − 3n) of order Y ′. The resulting path forest

$$\displaystyle \begin{aligned}\bigcup\limits_{i=1}^n Q_i^{X'}\cup \bigcup\limits_{i=1}^{m-3n} Q_i^{Y'}\end{aligned}$$

corresponds to $\bigcup _{i=1}^m P_{2i-1}$ and can thus be burnt in m steps. Next, we need to connect the graph by using caterpillars to keep the individual paths separated from each other. In order to do so, we need at most m + 1 caterpillars G ₁, …, G _m+1 whereby G _i has a spine of length 2(2m + 1 − i) + 1 with exactly one leg attached to each spine vertex (except the two terminal vertices). The caterpillars and the paths are arranged alternately until only caterpillars are left, which are then placed at the end. The subgraphs are connected through an edge between their end vertices. We denote the longest path in G by P _ℓ and get

$$\displaystyle \begin{aligned} \ell&=\Bigg|\bigcup\limits_{i=1}^n V\Big(Q_i^{X'}\Big)\Bigg|\cup \Bigg|\bigcup\limits_{i=1}^{m-3n} V\Big(Q_i^{Y'}\Big)\Bigg|\cup \Bigg|\bigcup\limits_{i=1}^{m+1} V\big(P_{2(2m+1-i)+1}\big)\Bigg|\\ &=\sum_{i=1}^{m}(2i-1)+ \sum_{i=1}^{m+1}(2(2m+1-i)+1) \\ &=\sum_{i=1}^{m}(2i-1)+ \sum_{i=m+1}^{2m+1}(2i-1) \\ &= (2m+1)^2. \end{aligned} $$

The inequality in the conjecture is tight for paths; thus $b(G)\geq b(P_\ell ) = \left \lceil \sqrt {\ell }\right \rceil =2m+1$. Due to the strong $\mathcal {N}\mathcal {P}$-completeness of Distinct 3-Partition, we can assume S to be in $\mathcal {O}\big (n^{\mathcal {O}(1)}\big )$ and as m is bounded by S, the caterpillar G is computed in polynomial time with regard to the input length. Further, we constructed the caterpillar G in such a way that if X can be partitioned into n triples, each of whose elements add up to S (and equivalently $Q_1^{X'},\dots,Q_n^{X'}$ can be partitioned into paths {P _i | i ∈ X′}), lighting the central spine vertex of caterpillar G _i in step i (for 1 ≤ i ≤ m + 1) and lighting the central vertex of path P _{2(2m+1−i)+1} in step i (for m + 2 ≤ i ≤ 2m + 1) burns the whole graph in 2m + 1 steps. Consequently, b(G) ≤ 2m + 1 holds and altogether, b(G) = 2m + 1.

To prove the opposite direction, we assume b(G) = 2m + 1 and let (x ₁, …, x _2m+1) be an optimal burning sequence for the caterpillar G. First, we can observe that x _i is a spine vertex for all 1 ≤ i ≤ 2m + 1 and the burning circles have to be pairwise disjoint as ℓ is a square number and $b(P_\ell )=\left \lceil \sqrt {\ell }\right \rceil$. Next, the largest burning circle has to cover G ₁ with spine P _2(2m+1)−1. Otherwise, at least two burning circles are needed which would have to intersect at two spine vertices to cover all legs as pictured in Fig. 6. Inductively, G _i has to be covered with the i-th largest burning circle; thus the central spine vertex of G _i has to be lit in the i-th step for all 1 ≤ i ≤ m + 1.

Fig. 6

If we do not cover G ₁ with the largest burning circles, at least two spine vertices are covered twice

Therefore, $\bigcup _{i=1}^{m+1}G_i$ will be burning after 2m + 1 steps induced by x ₁, …, x _m+1 and in the last m time steps x _m+2, …, x _2m+1 have to ignite $\bigcup _{i=1}^n Q_i^{X'}\cup \bigcup _{i=1}^{m-3n} Q_i^{Y'}=\bigcup _{i=1}^m P_{2i-1}$, i.e., the remaining subpaths need to be covered by

$$\displaystyle \begin{aligned}\bigcup\limits_{i=m+2}^{2m+1}\mathcal{N}_{2m+1-i}[x_i].\end{aligned}$$

As seen before the burning circles have to be disjoint; thus $\mathcal {N}_{2m+1-i}[x_i]$ has to cover a path of length 2(2m + 1 − i) − 1 for m + 2 ≤ i ≤ 2m + 1. Hence, each $Q^{Y'}_i$ for 1 ≤ i ≤ m − 3n is covered by itself and each $Q^{X'}_i$ for 1 ≤ i ≤ n is partitioned in paths of lengths X′. Since $\frac {S}{4}<a_i<\frac {S}{2}$ by assumption, each partition consists of three elements in X′, which add up to 2S − 3. By retranslating this 3-partition of X′ to X we obtain the sought-for partition into n triples each of whose elements sum up to S. □

As caterpillars are exactly the trees of pathwidth one the above theorem provides a statement about the complexity of graphs whose spanning trees are caterpillars.

Corollary 1

Burning Number is $\mathcal {N}\mathcal {P}$ -complete for graphs of pathwidth one.

4 The Burning Number Conjecture for p-Caterpillars

In this section, we turn the study to the more general case of p-caterpillars.

Definition 1 (p-Caterpillar)

A p-caterpillar G is a tree in which all vertices are within a distance p of a central spine P _ℓ = {v ₁, …, v _ℓ}, which is the longest path in G.

Further, r-legs of a given p-caterpillar are defined as disjoint subtrees of G − P _ℓ with depth r − 1, for r ≤ p, whose roots are in distance one of the spine. We denote the maximum length of all legs attached to spine vertex v _i by $p_{\max }(v_i)$ and the number of all vertices which are connected to the spine via v _i by p _Σ(v _i).

Thus, the parameter p indicates the maximum length of the legs and for every tree T there is a p such that T can be regarded as a p-caterpillar. Obviously, a 1-caterpillar denotes a ‘common’ caterpillar.

Proposition 2

For a p-caterpillar G it follows that $b(G)\leq \left \lceil \sqrt {\ell }\right \rceil +p$ . Thus, for $\left \lceil \sqrt {n}\right \rceil \geq \left \lceil \sqrt {\ell }\right \rceil +p$ the conjecture is proven to be true.

Using a similar idea as in the alternative proof of Theorem 1, we can prove the Burning Number Conjecture for 2-caterpillars.

Theorem 3 (Burning Number Conjecture for 2-Caterpillars)

The burning number of a 2-caterpillar G satisfies $b(G)\leq \left \lceil \sqrt {n}\right \rceil$.

Proof

As in the alternative proof of Theorem 1 we remove recursively the largest burning circles and thereby intend to reduce the number of vertices to fall below the next smaller square number. If $p_{\max }(v_{2k-2})\leq 1$ and $p_{\max }(v_{2k-1})=0$, we delete the vertices v ₁, …, v _2k−1 together with all adjacent legs and obtain a graph whose vertex number is at most $\left \lfloor \sqrt {n}\right \rfloor ^2$. In the case $p_{\max }(v_{2k-2})=2$ or $p_{\max }(v_{2k-1})\geq 1$ but $\sum _{i=1}^{2k-3}p_\varSigma (v_i)\geq 2$, removing the vertices v ₁, …, v _2k−3 with their adjacent legs as depicted in Fig. 7 suffices to undercut $\left \lfloor \sqrt {n}\right \rfloor ^2$ vertices in the remaining graph.

Fig. 7

We remove the grey vertices of the largest burning circle V ₁ in a 2-caterpillar

Analogously, for $\sum _{i=1}^{2k-2}p_\varSigma (v_i)= 1$ and $p_{\max }(v_{2k-2})\leq 1$ but $p_{\max }(v_{2k-1})\geq 1$, we remove v ₁, …, v _2k−2 with all adjacent legs. Hence, it remains to consider the cases

• (a) $\sum \limits _{i=1}^{2k-3}p_\varSigma (v_i)= 1$ with $p_{\max }(v_{2k-2})= 2$ and

• (b) $\sum \limits _{i=1}^{2k-3}p_\varSigma (v_i)= 0$ with $p_{\max }(v_{2k-2})=2$ or $p_{\max }(v_{2k-1})\geq 1$.

If in case (a) we additionally have

$$\displaystyle \begin{aligned} \sum_{i=2k-1}^{(2k-1)+(2k-3)-4}p_\varSigma(v_i) \geq 1\quad \text{ or }\quad p_{\max}\left(v_{(2k-1)+(2k-3)-3}\right)\leq 1, \end{aligned}$$

we arrange the two largest burning circles V ₁ and V ₂ with an overlap of two vertices as outlined in Fig. 8. We delete the vertices v ₁, …, v _{(2k−1)+(2k−3)−4} and, if

$$\displaystyle \begin{aligned} p_{\max}\left(v_{(2k-1)+(2k-3)-3}\right)\leq 1, \end{aligned}$$

we also remove vertex v _{(2k−1)+(2k−3)−3} with all its adjacent legs. Hence, at most n − (2k − 1) − (2k − 3) vertices are left.

Fig. 8

We arrange the two largest burning circles V ₁ and V ₂ with an overlap of two vertices

If, however, in case (a) we additionally have

$$\displaystyle \begin{aligned} \sum_{i=2k-1}^{(2k-1)+(2k-3)-4}p_\varSigma(v_i) =0\quad \text{ and }\quad p_{\max}\left(v_{(2k-1)+(2k-3)-3}\right)=2, \end{aligned}$$

we consider the three largest burning circles and position them as shown in Fig. 9. The removal of v ₁, …, v _{(2k−1)+(2k−3)−4} with all adjacent legs yields a graph with at most n − (2k − 1) − (2k − 3) − (2k − 5) − 1 vertices.

Fig. 9

We delete the grey vertices of the three largest burning circles V ₁, V ₂ and V ₃

Lastly, in case (b) we can assume without loss of generality that $\sum _{i=1}^{2k-3}p_\varSigma (v_i)= 0$ with $p_{\max }(v_{2k-2})=2$ or $p_{\max }(v_{2k-1})\geq 1$ holds for both ends of the spine (otherwise we can apply one of the cases above on the other end), i.e., additionally, we have $\sum _{i=1}^{2k-3}p_\varSigma (v_{\ell -i+1})= 0$. Considering the three largest burning circles again, we place V ₃ and V ₁ at the beginning of the spine if

$$\displaystyle \begin{aligned} \sum_{i=2k-2}^{(2k-5)+(2k-1)-2}p_\varSigma(v_{i})\geq 2 \end{aligned}$$

and at the end if

$$\displaystyle \begin{aligned} \sum_{i=\ell-(2k-2)+1}^{\ell-((2k-5)+(2k-1)-2)+1}p_\varSigma(v_{i})\geq 2. \end{aligned}$$

As outlined in Fig. 10, we place V ₂ at the respective other side of the spine and remove the vertices v ₁, …, v _{(2k−5)+(2k−1)−2} as well as v _ℓ, …, v _{ℓ−(2k−3)+1}, and v _ℓ, …, v _{ℓ−((2k−5)+(2k−1)−2)+1} as well as v ₁, …, v _2k−3, respectively.

Fig. 10

We delete the grey vertices of the three largest burning circles V ₁, V ₂ and V ₃

In the remaining case, both sums equal one, $p_\varSigma (v_{2k-1})=p_\varSigma \left (v_{\ell -(2k-1)+1}\right )=1$ and p _Σ(v _i) = 0 for all other (2k − 5) + (2k − 1) − 2 spine vertices at both ends. Thus, we incorporate V ₄, placing it next to V ₂ without overlap, and additionally remove 2k − 7 spine vertices, one of which has an adjacent leg.

This completes the proof of the Burning Number Conjecture for 2-caterpillars. □

Next, we prove the Burning Number Conjecture for 3-caterpillars with at least $2\left \lceil \sqrt {n}\right \rceil -1$ vertices of degree one.

Theorem 4

The burning number of a 3-caterpillar G with at least $2\left \lceil \sqrt {n}\right \rceil -1$ vertices of degree one satisfies $b(G)\leq \left \lceil \sqrt {n}\right \rceil$.

Proof

Assume G = (V, E) to be a minimum counterexample regarding the vertex number n. Hence, $b(G)>\left \lceil \sqrt {n}\right \rceil =:k$ and |L|≥ 2k − 1 with the notation L := {v ∈ V  | deg(v) = 1}. Deleting all leaves, the remaining graph G − L is a 2-caterpillar, for which the conjecture is proven to be true. Thus

$$\displaystyle \begin{aligned} b(G-L) \leq&\left\lceil\sqrt{n-\vert L\vert}\right\rceil \leq\left\lceil\sqrt{n-2k+1}\right\rceil \leq\left\lceil\sqrt{k^2-2k+1}\right\rceil\leq k-1. \end{aligned} $$

However, if G − L burns after $\left \lceil \sqrt {n}\right \rceil -1$ steps, using the same burning strategy, G can be burnt in $\left \lceil \sqrt {n}\right \rceil$ steps. This contradicts the assumption; so no counterexample exists. □

Finally, we can also prove the conjectured upper bound more general for p-caterpillars with at least $2\left \lceil \sqrt {n}\right \rceil -1$ disjoint legs of length p.

Theorem 5

For any p-caterpillar G with at least $2\left \lceil \sqrt {n}\right \rceil -1$ disjoint legs of length p, we have $b(G)\leq \left \lceil \sqrt {n}\right \rceil$.

Proof

Suppose G = (V, E) is a minimum counterexample regarding p and among these minimal regarding its order n. Now, let L _p be the set of all leaves at the end of p-legs. Then again, $b(G)>\left \lceil \sqrt {n}\right \rceil =:k$ and |L _p|≥ 2k − 1. Deleting L _p, the remaining graph G − L _p is a (p − 1)-caterpillar with at least 2k − 1 disjoint legs of length p − 1, and thus

$$\displaystyle \begin{aligned} b(G-L_p) \leq&\left\lceil\sqrt{n-\vert L_p\vert}\right\rceil \leq\left\lceil\sqrt{n-2k+1}\right\rceil \leq\left\lceil\sqrt{k^2-2k+1}\right\rceil\leq k-1. \end{aligned} $$

Now, if G − L _p burns after $\left \lceil \sqrt {n}\right \rceil -1$ steps, G can be burnt in $\left \lceil \sqrt {n}\right \rceil$ steps, a contradiction. □

5 Concluding Remarks

By the results of this paper, it remains to prove the conjecture for p-caterpillars, p ≥ 3, with less than $2\left \lceil \sqrt {n}\right \rceil -1$ disjoint p-legs to complete the proof of the conjectured bound for all connected graphs. Minimum counterexamples for these remaining graph classes can be characterised in great detail. We plan to investigate these characterisations to prove the conjecture in future work.