Let \(G\) be an undirected graph. An orientation \(\vec G\) of \(G\) is a directed graph in which every edge of \(G\) is assigned a direction. Directed graph burning is an iterative graph exploration process in which each round consists of two phases: spreading, then vertex selection. Each vertex is initially considered unburned. In the spreading phase, each burned vertex burns all of its out-neighbors. In the vertex selection phase, a vertex is chosen and burned. The burning number of a directed graph \(b(\vec G)\) is the minimum number of rounds necessary to burn all vertices of \(G\). The orientable burning number of an undirected graph \(G\), denoted \(B(G)\), is the maximum burning number across all orientations of \(G\). In this paper, we prove two main results. First, for any integer \(k\) between the minimum and maximum burning numbers of orientations of \(G\), there exists an orientation \(\vec G\) such that \(b(\vec G) = k\). We also determine the orientable burning number of wheels using a bound on the join of directed graphs.
Graph burning is an iterative process which serves as a simplified model for how contagion or influence propagates throughout a graph. Each vertex in a graph is considered either burned or unburned. At the beginning of the process, all vertices are considered unburned. A round of the burning process consists of two steps: first, every unburned vertex adjacent to a burned vertex is burned, then we select a (potentially unburned) vertex to burn which is called a source. The burning process is completed when all vertices are burned (after completing the round). To begin this process a single vertex, \(v_0\) of \(G\), is chosen as the first source to be burned, comprising the first round. During the next round, all vertices which share an edge with \(v_0\) are subsequently burned since they are adjacent to a vertex which has been burned in the previous round. To complete this round a new source in \(G\) must be chosen; optimally sources are unburned vertices, however, a burned vertex may have to be chosen as a source if no unburned vertices exist. Once every vertex in \(G\) is burned, the process ends.
The sequence of vertices chosen in each round is called the burning sequence. The minimum number of rounds it takes to burn all vertices in \(G\), is called the burning number of the graph, denoted \(b(G)\). Note that the number of elements in a burning sequence corresponds to the number of rounds, so a graph has burning number \(b(G)\) if and only if there exists a burning sequence of length \(b(G)\).
The burning number was introduced in \(2014\) by Bonato, Janssen, and Roshanbin [4, 5]. There have been two primary directions of study regarding the burning number. One focuses on resolving the burning number conjecture, namely that for any graph \(G\) on \(n\) vertices \(b(G) \leq \sqrt{n}\). Several papers [1] approach this topic directly but recently it has been proven by Norin and Jérémie that the burning conjecture holds asymptotically [12]. To this end, others have focused on refining bounds for specific families of graphs including unicyclic, triangle free, theta, and caterpillars [9, 10, 13, 14]. The other focus of study has been on computational complexity due to the potential applications of burning number to social networks. It has been shown by Bonato et al. that determining the burning number is \(NP\)-Hard for even classes as restricted as trees [2, 6]. More recently by Mondal, Rajasignh, Parthiban, and Rajasingh that it is \(APX\)-Hard and establish approximation algorithms [11]. For more information on graph burning, we direct the reader to the survey by Bonato [3].
In \(2020\), burning number for directed graphs was introduced formally by Janssen [8] after it was noted by Bonato et al. that the notion naturally transfers from the undirected to directed case. We denote a directed graph as \(\vec G\), and thus, its burning number as \(b(\vec G)\). The directed burning process is similar to the burning process, with the alteration that burned vertices now only burn their out-neighbors. We define burning sequence and burning number of directed graphs analogously to the undirected case.
Most recently, in \(2024\) the notion of the burning number of directed graphs was extended to the orientable burning number by Courtiel, Dorbec, Gima, Lecoq, and Otachi [7]. Let \(G\) be an unoriented graph. The orientable burning number is the maximum burning number across all orientations of \(G\). In their paper, it was shown that there is a polynomial-time algorithm to determine the exact orientable burning number of König-Evergáry graphs, and some relations between clique number, matching number, and orientable burning number were established. They also prove that determining the orientable burning number of a graph is NP-Hard in general, motivating the study of particular classes of graphs.
In this paper, we will continue to explore the orientable burning number. In Section 2 we will establish that the burning number of directed graphs is relatively stable under a small number of edge reversals. We use this result to prove our first main result, that all burning numbers between the orientable burning number and the burning number of an undirected graph \(G\) are achieved by some orientation of \(G\).
In Section 3 we prove a bound for an oriented version of the join of two graphs, and use that to determine the orientable burning number of all Wheel Graphs.
We now present some important notation that appears throughout the paper. We denote \(V(G)\) to be the set of all vertices in \(G\), and likewise \(V(\vec G)\) to be the set of all vertices in \(\vec G\). Note though that if \(\vec G\) is an orientation of \(G\) then \(V(\vec G)=V(G)\) and so the latter is often used in both contexts. We similarly denote \(E(G)\) as the set of all edges in an undirected graph \(G\), and \(E(\vec G)\) is the set of all directed edges in a directed graph \(\vec G\). If \(G\) is an undirected graph, we will denote the collection of all orientations of \(G\) by \(\mathcal{G}\). Then, we denote \(\vec G_{max}\) to be an orientation of \(G\) such that \(b(\vec G_{max})=\displaystyle{\max_{\vec G \in \mathcal{G}}}(b(\vec G))\). Similarly, we define \(\vec G_{min}\) to be an orientation of \(G\) with \(b(\vec G_{min})=\displaystyle{\min_{\vec G \in \mathcal{G}}}(b(\vec G))\). In directed graphs we will use \(N^+(v)\) to be the out-neighborhood of a vertex \(v\) and \(N^-(v)\) to be the in-neighborhood. We will extend this notation to \(N_i^+(v)\) for any \(i \in \mathbb{N}\) to be the set of vertices \(u\) for which there exists a directed path of length \(i\) from \(v\) to \(u\). Lastly, we define the orientable burning number \(B(G)\) for a graph \(G\) to be the largest burning number obtained for all orientations of \(G\).
First we will find that there must exist at least one orientation with burning number \(z\), for all \(z\) between the minimum and maximum burning numbers across all orientations of a graph \(G\). With this theorem, we have that given an upper and lower bound for the orientable burning number of \(G\) which are established by construction, all integer burning numbers between those numbers are realized as the burning number of some orientation of \(G\). Note that the following Lemma was stated in Courtiel et al. [7], but for the sake of completeness and to establish a common lower bound construction, we will prove that the burning number of every orientation of \(G\) is at least \(b(G)\) and that this bound is achieved by some orientation.
Lemma 2.1 (Courtiel et al. [7]). If \(\vec G\) is an orientation of an undirected graph \(G\), then \(b(\vec G)\geq b(G)\). Furthermore, there exists an orientation of \(G\), \(\vec G’\) such that \(b(\vec G’) = b(G)\).
Proof. Let \(\vec G\) be an orientation of an undirected graph, \(G\). Let \(S\) be a minimum burning sequence of \(\vec G\). Let \(v \in V(G)\). Since \(S\) is a burning sequence of \(\vec G\), \(v\) is burned by the end of the burning process of \(S\) on \(\vec G\). So there exists a \(i\)th-source \(s_i \in S\) such that there exists an \(s_i,v-\)directed path \(P\), in \(\vec G\) with length less than or equal to \(|S|-i\). Note that \(P\) is an undirected path in \(G\), so the burning process of \(S\) on \(G\) will burn \(v\) at latest by round \(i + (|S|-i) = |S|\) since \(s_i\) is the \(i\)th-source in the burning process of \(S\) on \(G\). Thus \(S\) is a burning sequence of \(G\). Then \(b(\vec G) \geq b(G)\). Therefore, if \(\vec G\) is an orientation of \(G\), then \(b(\vec G)\geq b(G)\).
We now show that there exists an orientation \(\vec G’\) of \(G\) such that \(b(\vec G’) = b(G)\). Let \(T\) be a minimum burning sequence of \(G\). We will orient the edges of \(G\) to create \(\vec G’\) by following the burning process of \(T\) on \(G\). In each round, for each vertex \(u\) that was burned in the burning process of \(T\) in that round but not chosen as source, there exists some adjacent vertex \(v\) such that \(v\) was burned in the previous round and \(\{v,u\} \in E(G)\). Orient each such edge \(\{v,u\}\) as \((v,u) \in E(\vec G’)\). After the burning process of \(T\) is complete, if there are any unoriented edges that remain, orient them arbitrarily. Note that by construction, every vertex burned by \(T\) is burned in \(\vec G’\) by the round it was burned in \(G\) by \(T\). Therefore \(b(G) \leq b(\vec G’) \leq |T| = b(G)\) hence, \(b(\vec G’) = b(G)\). \(\square\)
We now show that the reversal of a single edge in a directed graph \(\vec G\) will increase the burning number by at most one. This is followed by the corollary that the reversal of an edge can decrease the burning number by at most one.
Lemma 2.2. Let \(\vec G=(V,E)\) and \((u,v) \in E(\vec G)\). Let \(\vec G^\prime=(V,E^\prime)\) where \(E^\prime=(E\setminus\{(u,v)\})\cup\{(v,u)\}\). Then \(b(\vec G’)\leq b(\vec G)+1\).
Proof. Let \(\vec G\) and \(\vec G^\prime\) be defined as above. Let \(S=(s_1,s_2,\dots,s_k)\) be a minimum burning sequence of \(\vec G\). Then \(v\) is burned in some round, call it round \(r\), in the burning process of \(S\) on \(\vec G\). Consider the burning sequence \(S’ = (s_1,s_2,\dots,s_{r-1},v,s_{r}, \dots, s_k)\), so \(|S’| = |S|+1\). We seek to show that \(S’\) is a burning sequence of \(\vec G’\). We will show that if \(w \neq v \in V(G)\) was burned in round \(c\) by \(S\) on \(\vec G\), then \(w\) is burned by round \(c+1\) by \(S’\) on \(\vec G’\). Let \(w \neq v \in V(G)\) be burned in round \(c\) by \(S\) on \(\vec G\).
Suppose \(c<r\). Then \(w\) is burned before \(v\) by \(S\) in \(\vec G\). Hence there exists some \(s_j\) with \(j<r\) such that there exists an \(s_j,w\)-path \(P_w\in\vec G\) by which \(w\) is burned in round \(c\) by \(S\) on \(\vec G\). Note that \(v\notin P_w\) since \(c<r\). In particular, \(P_w\) does not contain the edge \((u,v)\). As such, \(P_w\) is still a directed path in \(\vec G’\) and \(w\) will be burned in round \(c\) by spreading along the edges of \(P_w\) in \(\vec G’\).
Suppose \(c \geq r\). Suppose that for all sources \(s\) in \(S\), every \(s,w\)-path which would burn \(w\) in round \(c\) includes the vertex \(v\). Note that any shortest path \(P_w\) from \(v\) to \(w\) in \(\vec G\) will not contain the edge \((u,v)\). Since \(v\) is burned in round \(r\) as a source in \(S’\), the vertices of \(P_w\) will be burned in order by spreading along the edges of \(P_w\) starting in round \(r\). Since \(P_w\) was a shortest path in \(\vec G\) from \(v\) to \(w\), it will burn \(w\) by round \(c\) in \(\vec G’\). Finally, suppose instead that there exists a source \(s_j\) with an \(s_j, w\)-path, \(P_w\), which does not include \(v\), such that \(w\) is burned in round \(c\) of \(S\) on \(\vec G\) by spreading along the edges of \(P_w\). Then \(P_w\) is a directed path in \(\vec G’\). Since \(s_j\) is selected as the source in round \(j+1\) in \(S’\), \(w\) will be burned at the latest in round \(c+1\) by spreading along the edges of \(P_w\) starting in round \(j+1\).
In all cases \(w\) is burned at or before round \(c + 1\) by \(S’\) in \(\vec G’\). Therefore \(S’\) is a burning sequence of \(\vec G’\) and \(b(\vec G’)\leq|S’|=|S|+1\). Thus, \(b(\vec G’) \leq b(\vec G) + 1\). \(\square\)
In other words, the previous lemma gives that the burning number can increase by at most one when reversing the direction of an edge. We note that the proof will follow the same if \(v\) is placed either before or after the source that burns \(u\). Also, the reader can be readily verified that this proof can be slightly altered to show that the burning number of an undirected graph increases by at most one after an edge deletion.
In the following corollary, we use the upper bound on edge reversal’s effect on burning number to establish a similar lower bound.
Corollary 2.3. Let \(\vec G=(V,E)\) with \((u,v) \in E(\vec G)\) and \(\vec G^\prime=(V,E^\prime)\) be directed graphs such that \(E^\prime=\big(E\setminus(u,v)\big)\cup\{(v,u)\}\). Then \(b(\vec G)-1\leq b(\vec G^\prime)\leq b(\vec G)+1\).
Proof. Let \(\vec G\) and \(\vec G^\prime\) be defined as above. By Lemma 2.2 \(b(\vec G)\leq b(\vec G’)+1\), so \(b(\vec G) – 1 \leq b(\vec G’)\). Note that since \(\vec G’\) is one edge reversal from \(\vec G\), Lemma 2.2 gives that \(b(\vec G’) \leq b(\vec G) + 1\), hence \(b(G)-1 \leq b(\vec G’) \leq b(G) + 1\). \(\square\)
Corollary 2.4. Let \(\vec G=(V,E)\) be a directed graph with \(e\in E\). Let \(\vec G’=(V,E\setminus\{e\})\). Then \(b(\vec G’) \leq b(\vec G)+1\).
Proof. Note that in Lemma 2.2 the existence of the reversed edge \((v,u)\) was not necessary for \(u\) or \(w\) to be burned by the process of \(S’\) on \(\vec G’\). Thus for \(\vec G\) and \(\vec G’\) defined above, for the edge \(e\in\vec G\) such that \(e\notin \vec G’\), it is the case that \(b(\vec G’)\leq b(\vec G)+1\) by the proof of Lemma 2.2. \(\square\)
We will now show that across all orientations of a graph, every possible directed burning number between the burning number of \(G\) and the orientable burning number of \(G\) is achieved by some orientation.
Theorem 2.5. Let \(G\) be an undirected graph. For all \(k \in \mathbb{N}\) such that \[\displaystyle{\min_{\vec G \in \mathcal{G}}(b(\vec G)) \leq k \leq \max_{\vec G \in \mathcal{G}} (b(\vec G))},\] there exists \(\vec G^* \in \mathcal{G}\) such that \(b(\vec G^*) = k\).
Proof. Let \(\vec G_{max}\) and \(\vec G_{min}\) be defined as previously mentioned. Assume for the sake of contradiction that there does not exist an orientation of \(G\) with burning number \(k\), for some \(b(\vec G_{min})< x< b(\vec G_{max})\). There exists some sequence of edges \((e_1,e_2,\dots,e_{\ell})\) such that reversing the edges \(e_1, e_2,\dots,e_\ell\) in \(\vec G_{min}\) results in the orientation \(\vec G_{max}\) and each edge appears at most once in the sequence. Note then that there exists a corresponding sequence of orientations of \(G\), denoted \((\vec G_0,\vec G_1,\vec G_2,\dots,\vec G_\ell)\) , with \(\vec G_0=\vec G_{min}\) such that \(\vec G_i\) is the orientation of \(G\) obtained by reversing the edge \(e_i\) in \(\vec G_{i-1}\) for all \(1\leq i\leq \ell\). Note then that \(\vec G_\ell=\vec G_{max}\). Then for any \(\vec G_i\) it is the case that \(b(\vec G_i)-1\leq b(\vec G_{i-1})\leq b(\vec G_i)+1\) by Lemma 2.2, since only one edge was reversed in \(\vec G_{i-1}\) to produce \(\vec G_i\). Then there exists some largest integer \(h<\ell\) such that \(b(\vec G_h)\leq k-1\). Then \(b(\vec G_{h+1})\geq k+1\) since we have assumed that no orientation of \(G\) has burning number \(k\). Thus, \(b(\vec G_{min})< b(\vec G_h)+1\leq k\leq b(\vec G_{h+1})-1< b(\vec G_{max})\) and so \(b(\vec G_h)+2\leq b(\vec G_{h+1})\). This is a contradiction with Lemma 2.2 since the single edge reversal \(e_{h+1}\) increased the burning number of \(\vec G_h\) by at least \(2\). Thus, there exists an orientation of \(G\), call it \(\vec G_j\), such that \(b(\vec G_j)=k\), for \(b(\vec G_{min})< k< b(\vec G_{max})\). Thus, for all \(k\in\mathbb N\) such that \(\displaystyle{\min_{\vec G \in \mathcal{G}}(b(\vec G)) \leq k \leq \max_{\vec G \in \mathcal{G}} (b(\vec G))}\), there exists \(\vec G^* \in \mathcal{G}\) such that \(b(\vec G^*) = k\). \(\square\)
With the results of this section, all possible burning numbers of orientations of a given graph \(G\) are established if one can determine both \(b(G)\) and \(B(G)\).
Observation 2.6. Let \(\vec G’=(V,E’)\) be a directed graph with \(w\in E’\). Let \(\vec G=(V,E)\) be a spanning subgraph of \(\vec G’\) such that \(E=E’\setminus\{w\}.\) Then, \(b(\vec G^\prime)<b(\vec G)+1\).
Proof. Since \(\vec G\) is a subgraph of \(\vec G’\), every edge of \(\vec G\) is an edge of \(\vec G’\), hence every burning sequence of \(\vec G\) is a burning sequence of \(\vec G’\). Thus, \(b(\vec G’)<b(\vec G)+1\). \(\square\)
Note that this means that when an edge is added to a graph, it can decrease the burning number by at most one. Because the previous proof relies on the particular burning sequences within a graph, and not the direction of any edges, a similar argument may also be applied to undirected graphs. Hence, we are left with the following corollary.
Corollary 2.7. Let \(G’=(V,E)\) be a graph containing some edge, \(e\). Let \(G=(V,E^\prime)\) be a graph where \(E^\prime=E\setminus\{e\}.\) Then \(b(G’) – 1 \leq b(G) \leq b( G’) + 1\).
Let \(\vec G\) and \(\vec H\) be directed graphs. We will denote directed graph operations as follows. A directed graph \(\vec D\) is called an oriented join of \(\vec G\) and \(\vec H\) if \(D\) has vertex set \(V(\vec G) \cup V(\vec H)\) and an edge set that contains exactly the edges \(E(\vec G) \cup E(\vec H)\) and an orientation of each pair \(\{u,v\}\) such that \(u \in V(\vec G)\) and \(v \in V(\vec H)\). Note that we define this directed graph products such that the underlying graphs \(G\) and \(H\) in the product maintain the orientation of all edges in \(\vec G\) and \(\vec H\). The reader should note that this restriction on the possible orientations is held throughout the section, in contrast to the previous section where we considered all possible orientations of underlying graphs.
Theorem 3.1. Let \(\vec G\) and \(\vec H\) be directed graphs. Let \(\vec D\) be an oriented join of \(\vec G\) and \(\vec H\). Then, \(b(\vec D)\leq max\{b(\vec G),b(\vec H)\}+1\).
Proof. Let \(S_G=(x_1,x_2,\dots,x_k)\) be a minimum burning sequence of \(\vec G\), and \(S_H=(y_1,y_2,\dots,y_\ell)\) be a minimum burning sequence of \(\vec H\). Without loss of generality, let \(k\geq\ell\). Let \(v\) be a vertex in \(\vec G\). Then there exists \(x_i \in S_G\) such that there exists an \(x_i,v\)-directed path \(P_G\), in \(\vec G\) with length less than or equal to \(|S_G|-i\). Since \(\vec D\) is an oriented join of \(\vec G\) and \(\vec H\), \(P_G\) is a path in \(\vec D\). Thus, if \(x_i\) is burned in the \(i+1^{th}\) round of \(S_G\) on \(\vec G\), \(v\) will be burned in or before round \(|S_G|+1\). Similarly, we have that if a vertex \(u\) is burned in \(H\) through a path that begins at \(y_j\) and \(y_j\) is burned by round \(j+1\), then \(u\) is burned by round \(|S_H| + 1\). We seek to show that there exists a sequence of vertices such that each source of \(S_G\) and \(S_H\) are burned at most one round after they are burned in \(S_G\) and \(S_H\).
We construct a proposed burning sequence \(S_ {D}\) such that \(S_D=(z_1,z_2,\dots z_m)\) where \(z_s = y_s\) if \((y_s,x_s)\in E(\vec D)\), and \(z_s = x_s\) otherwise. We now show that any source \(x_i\) in \(S_G\), the burning process of \(S_D\) on \(\vec D\) will burn \(x_i\) by round \(i+1\). If \(z_i=x_i\) so \(x_i\) is burned by round \(i\). Otherwise, \(z_i = y_i\) and \((y_i, x_i) \in E(\vec D)\), so \(x_i\) is burned by round \(i+1\). In either case, \(x_i\) is burned by round \(i+1\). Similarly, each source \(y_i\) in \(S_H\) must be burned by round \(i+1\). Hence, if \(v \in S_D\), is burned in round \(j\) in the burning processes of \(S_G\) on \(\vec G\) or \(S_H\) on \(\vec H\), \(v\) is burned by round \(j+1\) in the burning process of \(S_D\) on \(\vec D\). Thus, to guarantee that \(S_D\) is a burning sequence of \(\vec D\), we include one arbitrary vertex \(z_{k+1} \in \vec D\) at the end of \(S_D\). So \(S_D=(z_1,z_2,\dots, z_\ell,x_{\ell+1},\dots, x_k,z_{k+1})\) is a burning sequence of \(\vec D\) and \(\vert S_D\vert=k+1=\vert S_G\vert+1=max\{b(\vec G),b(\vec H)\}+1\). \(\square\)
The authors note that the proof of Theorem 3.1 uses very few of the edges between the two parts of an oriented join of two graphs. Indeed, this proof statement can be refined to the following: if \(\vec G\) and \(\vec H\) subgraphs of a directed graph \(\vec D\) such that \(V(\vec D) = V(\vec G) \cup V(\vec H)\) and there exists a pair of minimum burning sequences \(S_G = (x_1,x_2,\dots, x_k)\) of \(\vec G\) and \(S_H = (y_1,y_2,\dots, y_\ell)\) of \(\vec H\) with \(k \geq \ell\) such that for all \(1 \leq j \leq \ell\), either \((x_i, y_i) \in E(\vec D)\) or \((y_i, x_i) \in E(\vec D)\), then \(b(\vec D) \leq \max \{ b(\vec G), b(\vec H)\} + 1\). At its core, this proof is about finding a matching between two minimum burning sequences which saturates at least one of the sequences. This statement is quite cumbersome, so we leave the theorem as stated, but draw attention to the importance of a matching saturating a minimum burning sequence here as a link to results about the matching numbers of graphs and the orientable burning numbers, as proven by Courtiel et al. [7]. As an example, we resolve the orientable burning number of wheel graphs. We define the wheel graph \(W_k\) to be the graph obtained from the join of a single vertex and a cycle on \(k-1\) vertices.
Theorem 3.2. For any orientation of a wheel with \(k>6\) vertices, \(\vec G\), then \(2 \leq b(\vec G) \leq \lfloor \frac{k-1}{2} \rfloor\). Furthermore, the orientable burning number of the wheel on \(k\) vertices is \(\lfloor \frac{k}{2}\rfloor\).
Proof. Any orientation of a wheel graph is the join of a single vertex, call it \(v\) and an orientation of a cycle, \(\vec C\). We note that any even cycle on \(n\) vertices can be oriented such that \(\frac{n}{2}\) vertices have in-degree zero, hence must be chosen as sources in any burning sequence, which is the orientable burning number. Similarly, the orientable burning number of an odd cycle on \(n>3\) vertices is \(\frac{n-1}{2}\). Hence, by Theorem 3.1 the orientable burning numbers are upper bounded by \(\frac{n}{2} +1\) and \(\frac{n-1}{2} + 1\) respectively. Observe that \(v\) is incident to every source in any minimum burning sequence of \(\vec C\). Thus, every source in any minimum burning sequence of \(\vec C\) is adjacent to \(v\), and if any source other than the last one chosen directed to \(v\), the burning number of the orientation is at most \(\lfloor \frac{n}{2}\rfloor\). Otherwise, \(v\) has edges directed to every source but the last, so choosing it as the first source will burn all sources but the last in the second round. Since \(k>6\) the burning sequence of such an orientation takes no longer than the previous case. Hence, no orientation of \(W_k\) has burning number \(\lfloor \frac{k}{2}\rfloor +1\).
Finally, to show that the orientable burning number of the wheel is \(\lfloor \frac{k}{2}\rfloor\), one can verify that the orientation of \(W_k\) such that every edge between \(\vec C\) and \(v\) is directed to \(v\) and the edges of the cycle are oriented to achieve the orientable burning number of the cycle has burning number \(\lfloor \frac{k-1}{2} \rfloor\) by noting that this orientation has \(\lfloor \frac{k-1}{2}\rfloor\) vertices with in-degree \(0\) which must be chosen as sources. See Figure 1 for examples of orientations of \(W_ {7}\) and \(W_ {8}\) with the vertices that must be sources circled. \(\square\)
For the sake of completeness, we note that the orientable burning numbers of the small wheel graphs are as follows: \(\vec b ( W_4) = 2\) since every orientation of \(W_4\) contains at least one vertex with out-degree at least two, and \(\vec b(W_5) = \vec b(W_6) = 3\) since \(W_5\) and \(W_6\) can be oriented such that no vertex dominates all but one other vertex. Furthermore, in \(W_6\), the cycle of length \(5\) must include at least one path of length three, so taking the first vertex of that path as the first source leaves only a directed triangle which can be burned in two rounds.
Below we include a quick observation about partitioning the graph into (potentially) more than two subgraphs, namely into strongly connected components which give a weak bound on burning numbers. We say that a strongly connected component \(\vec H\) of a directed graph \(\vec G\) has in-degree zero if for all \(v \in V(\vec G) \setminus V(\vec H)\) and for all \(u \in \vec H\), \((v, u) \notin E(\vec G)\).
Observation 3.3. Let \(\vec G\) be a directed graph and \(C\) be the set of all strongly connected components in \(G\) with in-degree equal to zero. Then \(b(G) \geq |C|\).
Proof. Let \(\vec H \in C\) and suppose for contradiction that there exists a minimum burning sequence \(S\) of \(\vec G\) such that \(S \cap V(\vec H) = \emptyset\). Since all edges between vertices of \(\vec H\) and \(V(\vec G)\setminus V(\vec H)\) are oriented from \(V(\vec H)\) to \(V(\vec G)\setminus V(\vec H)\), the spreading stage of the burning process cannot burn any vertex in \(\vec H\) from \(V(\vec G) \setminus V( \vec H)\). Thus, the burning sequence of \(\vec G\) must include at least one vertex from each strongly connected component in \(\vec G\) with in-degree zero. \(\square\)
The burning number has been well studied, but the orientable burning number of a graph \(G\), which is the maximum burning number across all possible orientations of \(G\), was recently introduced by Courtiel et al. [7]. The orientable burning number serves as an upper bound for the burning number, and while this parameter searches for a maximum, in this paper we determine all possible directed burning numbers of across orientations of a graph \(G\). In Section 2 we proved that for any graph \(G\) all possible burning numbers of orientations of a graph between \(b(G)\) and \(B(G)\) are achieved by some orientation.
Theorem 4.1. Let \(G\) be an undirected graph. For all \(k \in \mathbb{N}\) such that \[\displaystyle{\min_{\vec G \in \mathcal{G}}(b(\vec G)) \leq k \leq \max_{\vec G \in \mathcal{G}} (b(\vec G))},\] there exists \(\vec G^* \in \mathcal{G}\) such that \(b(\vec G^*) = k\).
This result fills in all gaps of possible burning numbers of orientations of an undirected graph so that further study requires only to establish both the burning number and the orientable burning number of a graph. In this direction, Section 3 determines the orientable burning number of the wheel graphs by using a result about joins of directed graphs. The proof method involves breaking the graph into the two components of the graph product, and future directions may include more clever subgraph decomposition. The orientable burning number is still unknown for most classes of graphs, with the strongest result being an algorithm to determine in polynomial time the orientable burning number of König-Evergáry Graphs [7].
The authors declare no conflicts of interest.
This research received no external funding.
This study is theoretical and does not involve the generation or analysis of datasets.
All the authors contributed equally. All authors have read and agreed to the published version of the manuscript.