A note on graph burning of path forests

Graph burning is a discrete-time process introduced by Bonato et al. (2016) that can be viewed as a simplified model for the spread of contagion in a network. Given a simple finite graph $G$, each vertex of the graph is either burned or unburned throughout the process. Initially, every vertex of $G$ is unburned. At the beginning of every round $t\geq 1$, a burning source is placed at an unburned vertex to burn it. If a vertex is burned in round $t-1$, then in round $t$, each of its unburned neighbours becomes burned. A burned vertex will remain burned throughout the process. The burning process ends when all vertices of $G$ are burned, in which case we say the graph $G$ is burned. The burning number of $G$ is the least number of rounds needed for the burning process to be completed.

The study of graph burning is extensive, with the main open problem being the burning number conjecture by Bonato et al. (2016).

In the literature of graph burning, a graph is said to be $m$-burnable if its burning number is at most $m$, and a graph (including a disconnected graph) is said to be well-burnable if it satisfies the burning number conjecture. Many classes of graphs have been verified to be well-burnable, including hamiltonian graphs (Bonato et al., 2016), spiders (Bonato and Lidbetter, 2019; Das et al., 2018), and caterpillars (Hiller et al., 2021; Liu et al., 2020). Recently, the burning number conjecture was shown to hold asymptotically by Norin and Turcotte (2024).

The reader is referred to Bonato (2021) for a survey on graph burning. In this short note, we are interested in the graph burning of path forests. Here, a path forest is a disjoint union of paths. While not all path forests are well-burnable, it was shown in Tan and Teh (2023) that a path forest with a sufficiently long shortest path is well-burnable.

When determining whether a path forest is well-burnable, we can always extend some of its paths so that the order of the graph is $m^{2}$ for some $m\in\naturals$. So from here onwards, we will assume that the order of a path forest is always an integer squared. We say a path forest is deficient if it is not well-burnable, and by an $n$-path forest, we mean a path forest with $n$ paths.

The main purpose of this note is to provide insights on $L_{n}$, and some conjectures related to $L_{n}$. We clearly have $L_{1}=1$ as every path is well-burnable, and it is straightforward that $L_{2}=3$, since a $2$-path forest is deficient if and only if its path orders are $m^{2}-2$ and $2$ for some $m\geq 2$ (see Tan and Teh, 2020, Lemma 3.1). The study of the values of $L_{n}$ was posed as an open problem in Tan and Teh (2023), where it was mentioned that $L_{3}=18$ and $L_{4}=26$ (determined with careful analysis and the help of a computer).

Note that for a path forest of order $m^{2}$ to be well-burnable, a burning process of $m$ rounds must have its $i$th burning source burning exactly $2m-2i+1$ vertices, and every vertex is burned by exactly one burning source. So, each path in the path forest is burned exactly, and the number of burning sources used on the path has the same parity as its order. While investigating deficient $n$-path forests for some small values of $n$, we notice that when their shortest paths have orders slightly smaller than $L_{n}$, they are all trivially deficient, in the following sense. For such a deficient path forest, even if we pretend that for each of its paths, the $i$th burning source used on it (not on the path forest) would burn $2m-2i+1$ vertices, $m$ burning sources are not enough to completely burn the path forest, provided we insist that the number of burning sources used on each path has the same parity as its order. We will call these trivially deficient path forests impossibly burnable (this will be made more precise in Section 2).

As mentioned earlier, the answer to the above question is affirmative for small values of $n$ (up to $n=7$). However, what about the remaining values of $n$? While we are unable to verify for any $n\geq 8$ (due to computational limitations), we believe that the answer to the above question remains affirmative (see Conjecture 2.7). This belief has motivated us to study impossibly burnable path forests, which would lead to the computation of the exact values of $L_{n}$.

For $n\geq 2$, let $M_{n}$ be the smallest positive integer such that if $T$ is an impossibly burnable $n$-path forest, then its shortest path has order at most $M_{n}$. So assuming the answer to Question 1.2 is affirmative, it follows that $L_{n}=M_{n}+1$ for all $n\geq 2$. It is straightforward that $M_{2}=2$, and for the main result of this note, we determine the exact values of $M_{n}$.

We digress briefly to mention another formulation of the graph burning of path forests, presented in the form of a sumset partition problem. The problem of determining whether an $n$-path forest $(l_{1},l_{2},\ldots,l_{n})$ of order $m^{2}$ is well-burnable is equivalent to deciding whether the set of the first $m$ odd positive integers can be partitioned into $n$ subsets $S_{1},S_{2},\ldots,S_{n}$ such that for every $i\in[n]$, the sum of the numbers in $S_{i}$ is equal to $l_{i}$. Interested readers may refer to Ando et al. (1990), Chen et al. (2005), Enomoto and Kano (1995), Fu and Hu (1994), Lladó and Moragas (2012), and Ma et al. (1994) for some related studies on this formulation.

In this section, we will first describe our observations on deficient path forests that lead us to Question 1.2, and then we will proceed to prove Theorem 1.3. For a path forest, its path orders indicate the respective order of each of its paths. We may represent an $n$-path forest by an $n$-tuple $(l_{1},l_{2},\cdots,l_{n})$ of its path orders. Often, we assume $l_{1}\leq l_{2}\leq\cdots\leq l_{n}$, and if $T$ is a path forest, we may write $l_{1}(T)$ (or just $l_{1}$) for the order of its shortest path.

In Bessy et al. (2017), the graph burning problem was shown to be NP-complete for general path forests, and a polynomial time algorithm for the problem was constructed when the number of paths is fixed. Based on this algorithm, given the number of paths $n$ and a positive integer $M\geq n$, we are able to construct a complete list of well-burnable $n$-path forests of order $m^{2}$ for all $m\leq M$ using Matlab subject to computational limitations. Note that $(1,3,5,\ldots,2n-1)$ is the unique well-burnable $n$-path forest of order $n^{2}$. Our lists are constructed recursively based on the following strategy: to obtain a well-burnable $n$-path forest of order $(m+1)^{2}$,

1. 1.

   add a path of order $2m+1$ to any well-burnable $(n-1)$-path forest $T$ such that $|T|=m^{2}$; or

2. 2.

   add $2m+1$ vertices to any one of the paths of any well-burnable $n$-path forest $T$ such that $|T|=m^{2}$.

Suppose $T$ is a $3$-path forest of order $m^{2}$ and $l_{1}\geq 8$. From the complete list of well-burnable $3$-path forests for $m\leq 9$, we observe that if $T$ is deficient, then $T$ is one of the following six possibilities. Furthermore, if $m=9$, then $T$ is well-burnable. We can then deduce by induction that $T$ is well-burnable for any $m\geq 9$ by considering the $3$-path forest $(l_{1},l_{2},l_{3}-2m+1)$.

Similarly, we have the following observation for $4$-path forests.

It follows from Observations 2.1 and 2.2 that $L_{3}=18$ and $L_{4}=26$. Furthermore, as mentioned in the Introduction, we observed that all the deficient path forests in Observations 2.1 and 2.2 are impossibly burnable. We now give the precise definition of an impossibly burnable path forest.

Based on Observation 2.1 and the subsequent discussion, any deficient $3$-path forest with $l_{1}\geq 8$ is impossibly burnable. For the case of $4$-path forests, a Matlab search reveals that there are exactly $47$ deficient $4$-path forests with $l_{1}\geq 18$, all of which are impossibly burnable. Note, however, that the path forest $(17,17,17,30)$ is deficient, but it is not impossibly burnable. Analysing the cases for $5\leq n\leq 7$ gives similar results, leading us to the following conjecture.

As mentioned earlier, Conjecture 2.7 is true for $n=4$, but it is not true for $n=3$ as $L_{2}=3$. The path forest $(3,3,3)$ is deficient but not impossibly burnable. Through an extensive Matlab search, we have determined that $L_{5}=36$, $L_{6}=46$, and $L_{7}=56$. Here, we briefly mention our computational validation of Conjecture 2.7.

Analysing the list of well-burnable $5$-path forests order $m^{2}$ for $m\leq 18$, we observe that there are exactly $608$ deficient $5$-path forests with $l_{1}\geq 26$, all of which are impossibly burnable. Furthermore, all $5$-path forests of order $18^{2}$ with $l_{1}\geq 26$ are well burnable. Hence, we can again deduce by induction that for $m\geq 18$, every $5$-path forest of order $m^{2}$ with $l_{1}\geq 26$ is well-burnable. Similarly, Conjecture 2.7 holds true for $n=6$. Specifically, all the $5185$ deficient $6$-path forests with $l_{1}\geq 36$ are impossibly burnable. We have also managed to verify Conjecture 2.7 for $n=7$, with a more significant effort due to computational limitations. (See Appendix A for a brief account of this verification.)

As $M_{n}$ increases as $n$ grows by Theorem 1.3, we remark that Conjecture 2.7 implies a strongly affirmative answer to Question 1.2, resulting in $L_{n}=M_{n}+1$. We are now ready to determine the exact values of $M_{n}$.

For every $n\geq 4$, let $\Delta_{n}$ denote the least integer with the property that whenever $T$ is a deficient $n$-path forest with $l_{1}\geq\Delta_{n}$, then $T$ is impossibly burnable. In our verification of Conjecture 2.7 for small values of $n$, we have observed that $\Delta_{n}=L_{n-1}$ for $n\in\{4,5,6,7\}$. In fact, our conjectures propose that $\Delta_{n}$ exists and $\Delta_{n}\leq L_{n-1}$ for all $n\geq 4$. Upon further analysis using Matlab, we have found that there is only one deficient $7$-path forest with $l_{1}=45$ that is not impossibly burnable, namely, the path forest $(45,45,45,45,72,74,74)$, confirming $\Delta_{7}=L_{6}=46$. The scarceness of such deficient path forests has led us to anticipate the likelihood of $\Delta_{n}<L_{n-1}$ for larger $n$. The study of the values of $\Delta_{n}$ potentially poses another challenging open problem.

Theorem 1.3 implies that the values of $L_{n}$ are known if the answer to Question 1.2 is affirmative. However, although impossibly burnability is a simpler concept, Conjecture 2.7 is surprisingly nontrivial. Furthermore, as pointed out above, $L_{n-1}$ is not necessarily the tight lower bound on the order of the shortest path for the conclusion to be true, and thus its essentiality in a possible proof by induction is doubtful. As an alternative approach in light of Theorem 1.3, we now propose another conjecture, the truth of which implies a good asymptotic approximation to the values of $L_{n}$.

Note that $L_{n}\geq M_{n}+1$ for all $n\geq 2$. By Theorem 1.3, we have $M_{n}\sim 12n$. Therefore, assuming Conjecture 3.1 holds, it follows that $L_{n}\sim 12n$, that is, $\frac{L_{n}}{12n}\rightarrow 1$ as $n\rightarrow\infty$.

Henceforth, unless stated otherwise, $T$ is a $7$-path forest of order $m^{2}$ for some $m$. Note that when $l_{1}\geq 46$, $m$ is at least $18$. For $m$ up to $22$, we obtained the complete list of all well-burnable $7$-path forests of order $m^{2}$ and thus the corresponding list of deficient $7$-path forests thereafter. From here, it is easy to filter out those with $l_{1}\geq 46$. As a matter of fact, we saved the lists of well-burnable $7$-path forests for $m=21$ and $m=22$ in many parts, as the memory required for them to be saved as a single array is too large. Hence, we managed to verify Conjecture 2.7 (henceforth, our conjecture) for the case of seven paths for $m$ up to $22$ this way. However, we can no longer proceed in this manner for larger $m$. Therefore, in this appendix, we give a brief account on how we go around it. Table 1 gives some statistics from our Matlab search.

For convenience, we use the following definition.

Suppose $|T|=23^{2}$ and $l_{1}\geq 46$. Note that $l_{7}\geq 76$ and thus $l_{7}-45\geq 31$. If $T$ is deficient, then $T^{\prime}=(l_{1},l_{2},\ldots,l_{6},l_{7}-45)$ is deficient. Hence, we first identified all such path forests $T$ that are potentially deficient. Such $T$ can be obtained from a deficient $7$-path forest $T^{\prime}$ of order $22^{2}$ with $31\leq l_{1}^{\prime}\leq 45$ and $l_{2}^{\prime}\geq 46$ by extension at the first component or from a deficient $7$-path forest $T^{\prime}$ of order $22^{2}$ with $l_{1}^{\prime}\geq 46$ by extension at any of the seven components. This way, we obtained $36529$ potentially deficient $7$-path forests of order $23^{2}$ with $l_{1}\geq 46$. From here, we noticed immediately that $9572$ among them are impossibly burnable. Hence, to verify our conjecture for $m=23$, it suffices to check that the remaining $26957$ path forests are all well-burnable. To show this, we first extracted from the list of all deficient $7$-path forests with $m=22$, a sublist of those with $l_{1}\geq 1$ and $l_{2}\geq 46$. We exhaustively checked and found that for each of the $26957$ path forests $T$, at least one of its seven reductions is not in the said sublist and thus $T$ is well-burnable.

To deal with larger $m$, we obtained the following two lists.

1. List A.

   All $9612$ deficient $7$-path forests of order $23^{2}$ with $l_{1}\geq 42$.

2. List B.

   All $9931471$ deficient $7$-path forests of order $23^{2}$ with $l_{1}\geq 1$ and $l_{2}\geq 49$.

There are three ways to obtain a well-burnable path forest of order $23^{2}$ with its shortest path having order at least $42$:

1. 1.

   adding a path of order $45$ to any well-burnable $6$-path forest $T$ such that $|T|=22^{2}$ and $l_{1}\geq 42$;

2. 2.

   adding $45$ vertices to any of the paths of any well-burnable $7$-path forest $T$ such that $|T|=22^{2}$ and $l_{1}\geq 42$;

3. 3.

   adding $45$ vertices to the first path of any well-burnable $7$-path forest $T$ such that $|T|=22^{2}$, $l_{1}\leq 41$, and $l_{2}\geq 42$.

This way, we obtained the complete list of $65485064$ well-burnable $7$-path forests of order $23^{2}$ with $l_{1}\geq 42$. From here, List A was obtained.

Before we proceed, an observation about List A will be useful later. Among the $9612$ members of List A, there are only $40$ of them with $42\leq l_{1}\leq 44$ and none with $l_{1}=45$. Furthermore, $l_{7}\geq 207$ for each of the $40$ path forests. (Note that $B_{23}(205)=5$ while $B_{23}(207)=7$.)

Similarly, we obtained the complete list of $311596739$ well-burnable $7$-path forests of order $23^{2}$ with $l_{2}\geq 49$. From here, List $B$ was obtained.

From both List A and List B, we extracted the sublist of deficient $7$-path forests of order $23^{2}$ with $l_{1}\geq 42$ and $l_{2}\geq 49$ and they coincide. Hence, this gives an assurance that our lists are correct. Furthermore, for our purposes, some sublists from the lists we obtained are probably sufficient, but as things developed, we ended up with those lists, as well as other lists that are not reported here.

Now, suppose $|T|=24^{2}$ and $l_{1}\geq 46$. Note that $l_{7}-47\geq 36$. If $T$ is deficient, then $T^{\prime}=(l_{1},l_{2},\ldots,l_{6},l_{7}-47)$ is deficient. Hence, similarly, we first identified all such path forests $T$ that are potentially deficient. Such $T$ can be obtained from a deficient $7$-path forest $T^{\prime}$ of order $23^{2}$ with $36\leq l_{1}^{\prime}\leq 45$ and $l_{2}^{\prime}\geq 46$ by extension at the first component or from a deficient $7$-path forest $T^{\prime}$ of order $23^{2}$ with $l_{1}^{\prime}\geq 46$ by extension at any of the seven components. This way, we obtained $34959$ potentially deficient $7$-path forests of order $24^{2}$ with $l_{1}\geq 46$. From here, we noticed immediately that $1294$ among them are impossibly burnable. Hence, to verify our conjecture for $m=24$, it suffices to check that the remaining $33665$ path forests are all well-burnable.

Note that if one of the paths of $T$ has order $47$, then deleting this path would result in a $6$-path forest that is well-burnable because $L_{6}=46$. Furthermore, only $34$ among those $33665$ path forests have $l_{1}=46$ and only one among these $34$ path forests has $l_{2}\neq 47$, namely the path forest $(46,49,49,49,49,92,242)$, which is $24$-burnable as $(46,49,49,49,49,242)$ is $22$-burnable. Hence, filtering out those with $l_{1}\in\{46,47\}$, we are left with $10712$ path forests to be checked. If $T$ is any of the $10712$ path forests, we observed that $l_{1}\geq 49$ and found that at least one of its seven reductions is outside List B, and thus $T$ is well-burnable.

To deal with the case $m=25$, we consider the following three lists separately.

1. List C.

   All deficient $7$-path forests of order $25^{2}$ with $l_{1}\geq 46$ and $l_{7}\geq 95$.

1. List D.

   All deficient $7$-path forests of order $25^{2}$ with $l_{1}\geq 46$ and $91\leq l_{7}\leq 94$.

1. List E.

   All deficient $7$-path forests of order $25^{2}$ with $l_{1}\geq 46$ and $l_{7}=90$.

Suppose $|T|=25^{2}$ and $l_{1}\geq 46$. If $l_{7}=90$, then $l_{6}=90$ and thus $T$ is well-burnable because $(l_{1},\ldots,l_{4},l_{5}-45)$ is $20$-burnable as $L_{5}=36$. Hence, List E is empty.

Now, suppose $91\leq l_{7}\leq 94$ and thus $l_{6}\geq 89$. Consider the path forest $T^{\prime\prime}=(l_{1},\ldots,l_{5},l_{6}-47,l_{7}-49)$. If $T$ were to be deficient, then $T^{\prime\prime}$ would be among the $40$ members in List A specifically mentioned earlier as $42\leq l_{1}^{\prime\prime}\leq 45$. However, from our earlier observation, that would force $l_{5}\geq 207$, which is impossible as $l_{5}\leq l_{7}$. Hence, List D is empty as well.

To deal with List C, we first identified all $7$-path forests $T$ of order $25^{2}$ with $l_{1}\geq 46$ and $l_{7}\geq 95$ that are potentially deficient. Such $T$ can be obtained from a deficient (and impossibly burnable) $7$-path forest $T^{\prime}$ of order $24^{2}$ with $l_{1}^{\prime}\geq 46$ by extension at any of the seven components. This way, we obtained $5042$ path forests and $79$ among them are impossibly burnable. Hence, to verify our conjecture for $m=25$, it suffices to check that the remaining $4963$ path forests are all well-burnable.

Suppose $T$ is any of the $4963$ potentially deficient $7$-path forests. We noticed that the first path of $T$ is either $49,51,53,55$, or $57$. If the first path has order $49$, then deleting this path will result in a well burnable $6$-path forest as $L_{6}=46$. Hence, filtering out those where $l_{1}=49$, we are left with $751$ path forests. If any reduction $T^{\prime}$ of $T$ has $l^{\prime}_{1}\geq 46$ but is not impossibly burnable, then $T^{\prime}$ is well-burnable and thus is $T$. Filtering further based on this, we are left with a much shorter list of $45$ path forests. Suppose $T$ is any of the $45$ path forests. We noticed that one of the paths of $T$ has order $94$. Let $T^{\prime}$ be the $6$-path forest obtained from $T$ by deleting this path and deleting $47$ vertices from the longest path. Then $T^{\prime}$ is well-burnable as $L_{6}=46$ and thus $T$ is well-burnable. Therefore, the $79$ impossibly burnable $7$-path forests are the only deficient $7$-path forests of order $25^{2}$ with $l_{1}\geq 46$.

Before we proceed to $m=26$, we make a note that among the $79$ impossibly burnable path forests, there are exactly four with $l_{1}=53$, namely:

Suppose $|T|=26^{2}$ and $l_{1}\geq 46$. If $T$ is deficient, then $T^{\prime}=(l_{1},\ldots,l_{6},l_{7}-51)$ is deficient and $l_{7}-51\geq 46$. Hence, we first obtained the list of $7$-path forests $T$ of order $26^{2}$ with $l_{1}\geq 46$ that are potentially deficient. There are $292$ members in this list of potentially deficient path forests and among them, only four are impossibly burnable and they are extensions of the four above, namely:

Suppose $T$ is any of the remaining $288$ potentially deficient path forests. If the first path of $T$ has order $51$, then deleting this path will result in a well-burnable $6$-path forest as $L_{6}=46$ and thus $T$ is well-burnable. Hence, filtering out those where $l_{1}=51$, we are left with $14$ path forests where $l_{1}=53$ for each of them coincidently. However, the reduction of each of the $14$ path forests at the last component can no longer be one of the four impossibly burnable path forests for $m=25$ with $l_{1}=53$. It follows that $T$ is well-burnable.

Finally, we can see that no path forest of order $27^{2}$ with $l_{1}\geq 46$ is deficient. Suppose $T$ is one such path forest and is deficient. Then $T^{\prime}=(l_{1},\ldots,l_{6},l_{7}-53)$ is deficient and thus $T^{\prime}$ is one of the four impossibly burnable path forests for $m=26$ above. However, this implies that $l_{1}=53$ (so is $l_{2}=l_{3}=53$). Since $(l_{2},l_{3},\ldots,l_{7})$ is well-burnable as $L_{6}=46$, it follows that $T$ is well-burnable, which gives a contradiction. By induction, no path forest of order $m^{2}$ with $l_{1}\geq 46$ for $m\geq 27$ is deficient.

In this appendix, we provide some details about the careful analysis referred to in the proof of Theorem 1.3.

Suppose there is an $i\in B$ such that $t_{i}\leq 2$. Then we would have

and so Inequality (1) would become

As before, it can be shown that $|B|>0$; if $|A|=0$, then $l_{1}\leq 9n-18+\frac{9}{n}$; and if $|A|=1$, then $l_{1}\leq 9n-15-\frac{1}{n-1}$.

If $|A|\geq 2$, letting $s=2|A|+k$, following the same exact analysis would lead to

It is straightforward that in the range of $0<x<n$, the function $3x-\frac{10n-9}{n-x}$ is maximised when $x=n-\sqrt{\frac{10n-9}{3}}$, with the maximum value being $3n-2\sqrt{30n-27}$. Therefore, $l_{1}\leq 12n-2\sqrt{30n-27}-8$.

We now see that for $n\geq 3$,