The $2$-burning number of a graph

Proof. Since the edges of $H$ are present in $G$, any $2$-burning sequence for $H$ will also be a $2$-burning sequence for $G$. Moreover, using any $2$-burning sequence $s$ for $H$, the number of rounds until all vertices are blue in $H$ is at least as large as when $s$ is used as a $2$-burning sequence for $G$. Thus $b_2(G)\le b_2(H)$ and $t_2(G)\le t_2(H)$. 

Proof. Consider a $2$-burning sequence for $G$ and assume for a contradiction neither $v_1$ nor $v_2$ are sources. The vertex $v_1$ can only turn blue after its two neighbors are blue so $v_1$ turns blue after $v_2$. By symmetry, $v_2$ turns blue after $v_1$, which is a contradiction. 

Proof. By definition we know $rd(s)\ge len(s)$ so suppose for a contradiction that $rd(s)=len(s)$. Let $v$ be the last source vertex in $s$. Then $v$ has a degree two non-source neighbor $x$, and $x$ cannot turn blue until at least one round after $v$ turns blue, a contradiction. 

Proof. Observation 2.5 implies that each of the $n$ leaves of $G\circ K_1$ must be a source vertex in a $2$-burning sequence for $G\circ K_1$. Each vertex of $G$ is adjacent to only one leaf of $G\circ K_1$, thus there must also be a source vertex from among the vertices of $G$. Therefore, $n+1\le t_2(G\circ K_1)\le b_2(G\circ K_1)$.

It remains to show $b_2(G\circ K_1)\le n+1$. Let $v_1$ be any vertex of $G$ and label the rest of the vertices $v_2,\dots ,v_n$, according to a breadth-first search rooted at $v_1$. Let $T$ be the resulting breadth first search tree of $G$, so $v_1$ is the root of $T$ and if $v_i$ is the parent of $v_j$ in $T$ then $i<j$. Label the leaves of $G\circ K_1$ as $v_1\prime ,v_2\prime ,\dots ,v_n^{\prime }$ so that $v_i$ is adjacent to $v_i^{\prime }$ for $1\le i\le n$ and let $s=(v_1,v_2\prime ,v_3\prime ,v_4\prime ,\dots ,v_n^{\prime },v_1\prime )$.

When we run Algorithm $2$-burning on graph $G\circ K_1$ and sequence $s$, we see that for $t:2\le t\le n$, vertex $v_t^{\prime }$ is blue at round $t$ as is the parent of $v_t$ in $T$. Thus $v_t$ has two blue neighbors after round $t$ and will be blue by round $t+1$. Therefore, all vertices of $G\circ K_1$ are blue by round $n+1$ and $s$ is a $2$-burning sequence of length $n+1$ for $G\circ K_1$, proving that $b_2(G\circ K_1)\le n+1$. 

Proof. Let $G$ be a graph and $D\subseteq V(G)$ be a dominating set of cardinality $\gamma (G)$. We choose the vertices of $D$ (in any order) to be the first $\gamma (G)$ source vertices for $G$. At the end of round $\gamma (G)$, every vertex in $G-D$ is adjacent to a blue vertex. Thus, the process reduces to the $1$-burning process on $G-D$. 

Proof. Let $G$ be the spider graph $S_{n_1,n_2,..,n_r}$ and $v^{\ast }$ the central vertex. As discussed above, $G-v^{\ast }$ is the graph whose components are the paths with $n_i$ vertices for $1\le i\le r$. We denote by $H_i$ the $i$th component of $G-v^{\ast }$, which is a path with $n_i$ vertices. Let $x_i$ be the vertex of $H_i$ that is adjacent to $v^{\ast }$ and $y_i$ be the vertex of $H_i$ that is farthest from $v^{\ast }$. We construct $2$-burning sequences for $G$ using four cases that depend on the value of $k$. In each case below, when $n_i$ is even we choose $y_i$ and every other vertex of $H_i$ starting at $y_i$ to be a source. Thus we have $\frac{n_i}{2}$ sources from $H_i$ for the even paths. We will select $\frac{n_i+1}{2}$ sources from $H_i$ when $n_i$ is odd but the particular sources chosen from these paths will vary in different cases.

First consider the case $k=0$, which is illustrated for $S_{4,4,4,2,2}$ in Figure 2 (a). In this case, $n$ is odd. In addition to the sources chosen from the $H_i$, we also select $v^{\ast }$ as a source. So the number of sources is $1+\frac{1}{2}(n_1+n_2+\cdots +n_r)=1+\frac{n-1}{2}=\lceil \frac{n}{2}\rceil$. Every non-source vertex of $G$ is adjacent to two of these sources, so every vertex turns blue by round $\lceil \frac{n}{2}\rceil +1$ and thus $b_2(G)\le \lceil \frac{n}{2}\rceil +1$. In this case, the sources can be arranged in any order.

Next consider the case $k=1$, which is illustrated for $S_{3,4,4,2}$ in Figure 2(b). In this case, $n$ is even. Without loss of generality, let $H_1$ be the odd path. If $n_1=1$ let $y_1$ be a source, and if $n_1\ge 3$, let $y_1$ and its neighbor $z_1$ be sources, as well as every other vertex starting at $z_1$. In addition to the sources chosen from the $H_i$, we also select $v^{\ast }$ as a source. So the number of sources is $1+\frac{1}{2}(1+n_1+n_2+\cdots +n_r)=1+\frac{n}{2}=\lceil \frac{n}{2}\rceil +1$. Arrange the sources so that $v^{\ast }$ is the first and $y_1$ is the last. The remaining sources can appear in any order. Every non-source vertex is adjacent to two sources, so all vertices will turn blue and we have constructed a $2$-burning sequence for $G$. Furthermore, the only neighbor of the last source $y_1$ is itself a source vertex, thus all vertices are blue by round $\lceil \frac{n}{2}\rceil +1$, and hence $b_2(G)\le \lceil \frac{n}{2}\rceil +1$.

Our third case is $k=2$, which is illustrated for $S_{5,3,4,2}$ in Figure 2 (c). In this case, $n$ is odd. Without loss of generality, let $H_1$ and $H_2$ be the odd paths, and for these paths (as well as the even ones) let $y_i$ and and every other vertex starting at $y_i$ be a source. This means that $x_1$ and $x_2$ will be chosen as sources. In this case we do not select $v^{\ast }$ to be a source, but we do select $x_1$ and $x_2$ as the first two sources so $v^{\ast }$ will turn blue in round $3$. The number of sources is $\frac{1}{2}(2+n_1+n_2+\cdots +n_r)=\frac{1}{2}(1+n)=\lceil \frac{n}{2}\rceil$. Since $k=2$ and $r\ge 3$, we know $n\ge 5$ so $\lceil \frac{n}{2}\rceil \ge 3$ and there are a sufficient number of rounds for $v^{\ast }$ to turn blue. After all the sources turn blue, every non-source is adjacent to two blue vertices, so in one additional round, all the vertices become blue. Thus $b_2(G)\le \lceil \frac{n}{2}\rceil +1$.

Finally, we consider the case $k\ge 3$, which is illustrated for $S_{5,3,3,3,3,4}$ in Figure 2(d). Without loss of generality, assume that $n_i$ is odd for $1\le i\le 3$. For the odd path $H_1$, if $n_1=1$ let $y_1$ be a source, and if $n_1\ge 3$, let $y_1$ and its neighbor $z_1$ be sources, as well as every other vertex starting at $z_1$. For the remaining odd paths (as well as the even ones), let $y_i$ and every other vertex starting at $y_i$ be a source. This means that $x_2$ and $x_3$ will be sources. In this case we do not select $v^{\ast }$ to be a source, but we do select $x_2$ and $x_3$ as the first two sources so $v^{\ast }$ will turn blue in round $3$ and we select $y_1$ to be the last source. The remaining sources can appear in any order. There are $\frac{n_i}{2}$ sources for each $H_i$ when $n_i$ is even and $\frac{1+n_i}{2}$ sources for each $H_i$ when $n_i$ is odd. Thus the number of source vertices is $\frac{1}{2}(k+n_1+n_2+\cdots +n_m)=\frac{1}{2}(n+k-1)$. Note that this number is an integer since $k$ and $n$ have opposite parity. Every non-source vertex is either adjacent to two sources or to $v^{\ast }$ and one source, so all vertices will turn blue and we have constructed a $2$-burning sequence for $G$. Furthermore, the only neighbor of the last source $y_1$ is itself a source vertex, thus all vertices are blue by round $\frac{1}{2}(n+k-1)$, hence $b_2(G)\le \frac{1}{2}(n+k-1)$.

It remains to show that $b_2(G)\ge \lceil \frac{n}{2}\rceil +1$ for $k\le 2$ and $b_2(G)\ge \frac{1}{2}(n+k-1)$ for $k\ge 3$. We begin by calculating the minimum number of source vertices in $H_i$ in a $2$-burning sequence. Of the vertices of $H_i$, vertex $y_i$ is a leaf of $G$ and the remaining $n_i-1$ vertices have degree 2 in $G$. By Lemma 2.6, at least $\frac{n_i-2}{2}$ of these degree two vertices must be sources and by Observation 2.6, the leaf $y_i$ must also be a source. Thus there are at least $\frac{n_i}{2}$ vertices in $H_i$ that are sources. Summing over all $i$, we get at least $\lceil \frac{n-1}{2}\rceil$ sources from $G-v^{\ast }$ in any $2$-burning sequence of $G$.

In the first case, $k=0$, so $n$ is odd and the number of sources from $G-v^{\ast }$ in any $2$-burning sequence is at least $\lceil \frac{n}{2}\rceil –1$. If none of the $x_i$ are sources, then $v^{\ast }$ must be a source, so there are at least $\lceil \frac{n}{2}\rceil$ sources. However, in this instance, every non-source has degree $2$ and every source is adjacent to a non-source, so by Lemma 2.7, the $2$-burning sequence requires $\lceil \frac{n}{2}\rceil +1$ rounds. If exactly one of the $x_i$ are sources, then again $v^{\ast }$ must be a source, so there are at least $\lceil \frac{n}{2}\rceil +1$ sources. Otherwise, at least two of the $x_i$ are sources and again there are at least $\lceil \frac{n}{2}\rceil +1$ sources. Thus any $2$-burning sequence requires at least $\lceil \frac{n}{2}\rceil +1$ rounds and $b_2(G)\ge \lceil \frac{n}{2}\rceil +1$.

In the next case, $k=1$, so $n$ is even and the number of sources from $G-v^{\ast }$ in any $2$-burning sequence of $G$ is at least $\lceil \frac{n}{2}\rceil$. If only one $x_i$ is a source then $v^{\ast }$ must be a source, so in any case there are at least $\lceil \frac{n}{2}\rceil +1$ sources. Thus any $2$-burning sequence requires at least $\lceil \frac{n}{2}\rceil +1$ rounds and $b_2(G)\ge \lceil \frac{n}{2}\rceil +1$.

In the case $k=2$ we again have $n$ odd and we may assume that the odd paths are $H_1$ and $H_2$. In any $2$-burning sequence there are at least $\frac{1+n_i}{2}$ sources from the odd path $H_i$ for $i=1,2$, so the total number of sources from $G-v^{\ast }$ is it least $\frac{1}{2}(2+n_1+n_2+\cdots +n_r)=\lceil \frac{1+n}{2}\rceil =\lceil \frac{n}{2}\rceil$. Suppose for a contradiction that there exists a $2$-burning sequence $s$ with $len(s)=rd(s)=\lceil \frac{n}{2}\rceil .$ Consider the last source $s_k$ of $s$ (i.e., $k=\lceil \frac{n}{2}\rceil$). If $s_k=x_1$ or $s_k=x_2$ then $v^{\ast }$ does not turn blue until round $\lceil \frac{n}{2}\rceil +1$, a contradiction. Otherwise, $s_k$ is adjacent to a degree $2$ non-source vertex and that vertex does not turn blue until round $\lceil \frac{n}{2}\rceil +1$, a contradiction. Thus any $2$-burning sequence requires at least $\lceil \frac{n}{2}\rceil +1$ rounds and $b_2(G)\ge \lceil \frac{n}{2}\rceil +1$.

Finally, we consider the case $k\ge 3$. In any $2$-burning sequence for $G$ there are at least $\frac{n_i}{2}$ sources from each $H_i$ when $n_i$ is even and at least $\frac{1+n_i}{2}$ sources from each $H_i$ when $n_i$ is odd. Thus the total number of source vertices is at least $\frac{1}{2}(k+n_1+n_2+\cdots +n_r)=\frac{1}{2}(k+n-1)$ and consequently $b_2(G)\ge \frac{1}{2}(k+n-1).$ 

Proof. In the proof of Theorem 3.1 we show that for $k=0$ and $k=2$, every $2$-burning sequence $s$ has $len(s)\ge \lceil \frac{n}{2}\rceil$ and there exists a $2$-burning sequence of that length. Thus when $k=0$ or $k=2$ we have $t_2(G)=b_2(G)–1$. When $k=1$ the proof shows that $len(s)\ge \lceil \frac{n}{2}\rceil +1$ for any $2$-burning sequence $s$, hence $t_2(G)=b_2(G)$. Finally, when $k\ge 3$ we show $len(s)\ge \frac{1}{2}(n+k–1)$ in the proof of Theorem 3.1, so $t_2(G)=b_2(G)$. 

Proof. Let $v^{\ast }$ be the central vertex of $W_n$ and label the vertices along the cycle consecutively as $1,2,3,\dots ,n$ where $n\ge 5$. We consider two possibilities for $2$-burning sequences for $W_n$: those for which $v^{\ast }$ is a source and those for which $v^{\ast }$ is not a source. Note that it is not useful to choose $v^{\ast }$ as a source in round 3 or later since it will be adjacent to the first two source vertices and will therefore turn blue at round 3. Additionally, note that selecting $v^{\ast }$ as the source in round 2 is equivalent to selecting it as the source in round 1, so we consider the latter in Case 1.

The central vertex $v^{\ast }$ is the first source.

Observe that in this case, once the central vertex turns blue, each vertex in the cycle is adjacent to one blue vertex, namely $v^{\ast }$, so it will turn blue when it is chosen as a source or when it is adjacent to another blue vertex of the cycle. This reduces the problem to finding the $1$-burning number for $C_n$, and adding one for the initial round of selecting $v^{\ast }$ as a source. In [6], it is proven that $b_1(C_n)=\lceil \sqrt{n}\rceil$, hence in Case 1, the minimum number of rounds for all vertices to turn blue is $1+\lceil \sqrt{n}\rceil$.

The central vertex $v^{\ast }$ is not a source vertex.

Let $s=(s_1,s_2,\dots ,s_m)$ be a $2$-burning sequence for which $s_i\ne v^{\ast }$ for $1\le i\le m$. Let $k=rd(s)$, so $3\le m\le k$. Apply Algorithm $2$-burning with input $W_n$ and sequence $s$. In round $3$ the central vertex $v^{\ast }$ turns blue. After that, each vertex with a blue neighbor on the cycle becomes blue in the next round. In round $4$, the neighbors of $s_1$ on the cycle turn blue (if they are not already blue) and in round $5$ their neighbors on the cycle turn blue, and this continues propagating outward along the cycle in both directions from $s_1$. Thus at each round, starting at round $4$, vertex $s_1$ is responsible for at most two new blue vertices, so after $k$ rounds, source $s_1$ turns at most $2(k-3)$ vertices of the cycle blue. The same is true for sources $s_2$ and $s_3$. For $j\ge 4$, source $s_j$ is responsible for turning at most $2$ of the cycle vertices blue in each round from $j+1$ to $k$, so it turns at most $2(k-j)$ vertices of the cycle blue in total. Let $B$ be the set of blue vertices in the cycle after $k$ rounds, thus $|B|\le m+3\cdot 2(k-3)+\sum _{j=4}^{m}2(k-j)$.

We simplify this sum to $$\begin{array}{rl}|B|\le & m+6k-18+2\sum _{j=4}^{m}k–2\sum _{j=4}^{m}j\\ =& m+6k–18+2k(m-3)–(m+4)(m-3)\\ =& 2km–m^2-6=m(2k-m)-6.\end{array}$$ There are $n$ vertices on the cycle, and all are blue after round $k$, thus $n\le m(2k-m)-6$. The product $m(2k-m)$ is maximized when $k=m$, so $n\le k^2-6$ or equivalently $k\ge \sqrt{n+6}$. We know $k$ is an integer, so in fact, $k\ge \lceil \sqrt{n+6}\rceil$. Hence when $v^{\ast }$ is not a source vertex, every $2$-burning sequence for $W_n$ requires at least $\lceil \sqrt{n+6}\rceil$ rounds and at least $m$ source vertices where $m(2k-m)\ge n+6$.

Next we show that the quantity $\lceil \sqrt{n+6}\rceil$ is also sufficient. Let $k=\lceil \sqrt{n+6}\rceil$ so $k^2\ge n+6$. Choose $m$ so that $2km–m^2\ge n+6$, but $2kr–r^2<n+6$ for $r<m$. That is, $m$ is the minimum integer for which $m(2k–m)\ge n+6$. Note that $m$ is well-defined since for $r=0$ we know $0<n+6$ and for $r=k$ we know $k^2\ge n+6$. We construct a $2$-burning sequence $s=(s_1,s_2,\dots ,s_m)$ and show that $rd(s)\le k$. This is illustrated in Figure 3 for $n=30$ (where $k=6$ and $m=6$) and for $n=26$ (where $k=6$ and $m=4$). Select the source vertices as follows. Let $s_1=1$,  $s_2=s_1+2(k-3)+1$, and $s_3=s_2+2(k-3)+1$. For $4\le j\le k$, let $s_j=s_{j-1}+(k-j+1)+(k-j)+1$. One can check that $m\le 3$ only when $n\le 9$, and in each of those cases our sequence $s$ is a $2$-burning sequence for $W_n$. Thus we may assume $m\ge 4$.

By the end of round $3$, the source vertices $s_1,s_2,s_3$ are blue as is the central vertex $v^{\ast }$. Once $v^{\ast }$ is blue, each uncolored vertex with a blue neighbor on the cycle becomes blue in the next round. First consider vertices $v$ with $s_1<v<s_2$. By construction, there are $2(k-3)$ such vertices, so each is distance at most $k-3$ from one of $s_1,s_2$ along the cycle. Since $s_1,s_2$ and $v^{\ast }$ are all blue by round 3, and there are $k$ rounds total, vertex $v$ will be blue after round $k$. The same is true for $s_2<v<s_3$.

Next consider vertices $v$ with $s_{j-1}<v<s_j$ for some $j$ with $4\le j\le m$. By construction, $s_j–s_{j-1}=1+(k-j+1)+(k-j)$, so there are there are $(k-j)+(k-(j-1))$ vertices strictly between $s_j$ and $s_{j-1}$ along the cycle. The $k-j$ vertices closest to $s_j$ all turn blue by round $k$ since $s_j$ turns blue at round $j$ and there are $k-j$ rounds remaining. Similarly, the $k-(j-1)$ vertices closest to $s_{j-1}$ all turn blue by round $k$. Thus again, vertex $v$ will be blue after round $k$.

Finally, we consider the vertices $v$ with $s_m<v<n$. As before, the $k-3$ vertices closest to $s_1$ along the cycle are all blue after round $k$, so it suffices to consider $v$ with $s_m<v\le n-(k-3)$. Using our recursive formulas above, we can derive explicit formulas for the source vertices. In particular, $s_1=1,$ $s_2=2+2(k-3),$ $s_3=3+4(k-3),$ and $$\begin{array}{rl}{s}_m=& m+3(k-3)+(k-m)+2\sum _{i=3}^{m-1}(k-i)\\ =& 4k-9+2\sum _{i=3}^{m-1}k–2\sum _{i=3}^{m-1}i\\ =& 4k-9+2k(m-3)-(m+2)(m-3)\\ =& 2km–m^2+m-2k–3.\end{array}$$

Hence, $s_m+(k-m)=2km–m^2–k–3\ge n+6–k–3=n–(k-3)$. Since $s_m$ turns blue in round $m$ and there are $k-m$ rounds remaining, the vertices $v$ with $s_m<v\le n-(k-3)$ will all be blue after round $k$. Thus $s$ is a $2$-burning sequence for $W_n$ and $rd(s)\le k=\lceil \sqrt{n+6}\rceil$. Hence we have shown that when $v^{\ast }$ is not a source, the minimum number of rounds for all vertices of $W_n$ to turn blue is $\lceil \sqrt{n+6}\rceil$.

Combining the results of these cases, we conclude that $b_2(W_n)=min\{1+\lceil \sqrt{n}\rceil ,\lceil \sqrt{n+6}\rceil \}$. By inspection, $b_2(W_4)=3$, and it is not hard to show that $\lceil \sqrt{n+6}\rceil \le 1+\lceil \sqrt{n}\rceil$ for $n\ge 5$, completing the proof. 

Proof. Fix an integer $r$ and choose an integer $k\ge 5$ such that $2(k-1)>r^2$. Let $n=(k-1{)}^2-5$, so $n+6=(k-1{)}^2+1=k^2–2(k-1)$, and thus $\lceil \sqrt{n+6}\rceil =k$. By Theorem 3.3 we know that $b_2(W_n)=k$ and by Corollary 3.4 we know that $t_2(W_n)$ is the smallest integer $m\ge 3$ for which $m(2k-m)\ge n+6.$ Observe that for $j=k-r$ we have $$j(2k-j)=(k-r)(k+r)=k^2–r^2>k^2–2(k-1)=n+6.$$ Hence $m\le k-r$ and $b_2(W_n)–t_2(W_n)=k-m\ge r$ as desired.