Characterization of $Q$ graph by the burning number

1.   Introduction

All graphs considered in this paper are finite and simple. We use Bondy and Murty ^[1] for notation and terminology not defined here. The concept of burning graph is introduced by Bonato ^[2] as a model for social contagion, and it was also studied by Janssen and Roshanbin ^[3,4]. Graph burning is inspired by graph theoretic processes like graph cleaning ^[5], and firefighting ^[6]. Given a finite connected graph, the process of burning a graph begins with all vertices being unburned. At time step 1, a single vertex is chosen to be burned. In each subsequent time step, a new vertex is burned and previously burning vertices burn their neighbors. This implies that if a vertex is already burned at step $t-1$, then its unburned neighbors (if any) become automatically burned at the end of step $t$. The process is completed when all vertices of the graph have been burned. The minimum number of time steps required to burn all the vertices of a graph $G$ is called the burning number of $G$ and denoted by $b(G)$. The significance of the burning number is that the speed of the spread of a contagion varies in reverse to the burning number of the respective graph model. For example, $b(K_n) = 2$, when $n \geq2$. Suppose that we burn a graph $G$ in $k$ steps in a burning process. The sequence $(x_1, \ldots, x_k)$ is called a burning sequence for $G$. The burning number of a graph $G$, denoted by $b(G)$, is also the length of a shortest burning sequence for $G$. Such a burning sequence is called an optimal burning sequence for $G$.

The burning problem is NP-complete even for trees and path-forests ^[4]. Thus, it is also interesting to determine the burning number of special classes of graphs. Bonato and Lidbetter ^[7] considered the bounds on the burning numbers of spiders (which are trees with exactly one vertex of degree strictly greater than two) and path-forests. Sim et al. ^[8] studied the burning number of generalized Petersen graphs. Mitsche et al. ^[9] established the burning number of graph products. Recently, Mitsche et al. ^[10] focused on a few probabilistic aspects of the burning problem. Very recently, Liu et al. ^[11,12] considered the burning number of theta graphs, path forests, and spiders.

In 2016, Bonato et al. ^[3] studied the burning number of paths and cycles, and based on these results, they proposed a conjecture on the upper bound for the burning number.

Theorem 1.1. For a path $P_{n}$ or a cycle $C_{n}$ of order $n$, we have $b(P_{n}) = b(C_{n}) = \lceil\sqrt{n}\thinspace\thinspace\rceil$. Moreover, if $G$ is a graph of order $n$ with a Hamiltonian path, then $b(G)\leq\lceil\sqrt{n}\thinspace\thinspace\rceil$.

Conjecture 1.2. For a connected graph $G$ of order $n$, $b(G)\leq\lceil\sqrt{n}\thinspace\thinspace\rceil$.

The $Q$ graph, often denoted by $Q_{v}(s, t_1, t_2)$, is obtained by joining one vertex of cycle $C_{s+1}$ with one vertex of path $P_{t+1}$ as $v$, where $t_1+t_2 = t$ and $t_1\geq t_2$, see Figure $1$. We call $Q_{v}(s, t_1, t_2)$ single tail $Q$ graph if $t_2 = 0$, simplifies as $Q_{v}(s, t)$, and double tails $Q$ graph if $t_2\geq 1$. Clearly, $Q$ graph is formed by identifying two vertices of cycle and path.

In this paper, we determine the burning number of the $Q$ graph and characterize $Q$ graph by the burning number. For a simple undirected graph $G$ which has vertex set $V(G)$ and edge set $E(G)$ and $v\in V(G)$, the eccentricity of $v$ is $ecc(v) = max\{d(v, u): u\in V(G)\}$, where $d(v, u)$ represents the distance of the shortest path from $v$ to $u$. The radius and diameter of $G$ are defined as $r(G) = min\{ecc(v):v\in V(G)\}$ and $d(G) = max\{ecc(v):v\in V(G)\}$, respectively. Here we list some known results.

A spider graph $S_{v}$ is a tree with exactly one vertex $v$ of degree strictly greater than two and $v$ is the center of the spider. A spider $S_{v}$ with $r$ arms can be thought of as $P_{a_{1}}\cup P_{a_{2}}\cup\ldots\cup P_{a_{r}}$, where the $P_{a_{i}}$ are edge-disjoint paths that share one common end vertex $v$. Then, $S_{v}$ is also denoted as $S_{v}(a_{1}, a_{2}, \ldots, a_{r})$.

Proposition 1.3. ^[7] Let $G = S_{v}(a_{1}, a_{2}, \ldots, a_{r})$ be a spider graph of order $n$. Then, $b(G)\leq \lceil\sqrt{n}\thinspace\thinspace\rceil$.

Proposition 1.4. ^[3] For a graph $G$, we have that $b(G) = min\{ b(T): {{T \;is \;a \;spanning \;tree \;of\; G}}\}.$

Proposition 1.5. ^[3] Burning a graph $G$ in $k$ steps is equivalent to finding a rooted tree partition into $k$ trees $T_1, T_2, \ldots, T_k$, with heights at most $(k-1), (k-2), \ldots, 0$, respectively, such that for every $1\leq i, j\leq k$, the distance between the roots of $T_i$ and $T_j$ is at least $|i-j|$.

Proposition 1.6. ^[3] For any graph $G$ with radius $r$ and diameter $d$, we have that $\lceil (d+1)^{1/2}\thinspace\rceil\leq b(G)\leq r+1$.

Proposition 1.7. ^[3] Let $H$ be an isometric subgraph of a graph $G$ such that, for any node $x \in V(G)\setminus V(H)$, and any positive integer $r$, there exists a node $f_r(x)\in V(H)$ for which $N_r[x]\cap V(H)\subseteq N{^H_r}[f_r(x)]$. Then, $b(H)\leq b(G)$.

Proposition 1.8. ^[12] Let $G = P_{a_1}\cup P_{a_2}$ with $a_1\geq a_2\geq 1$ and $J(t) = \{(t^{2}-2, 2)\}$ for integer $t\geq 2$. Then,

Proposition 1.9. ^[12] Let $G = P_{a_1}\cup P_{a_2}\cup P_{a_3}$ with $a_1\geq a_2\geq a_3\geq 1$. Then,

Let $J^{i}$ for $1\leq i\leq 5$ satisfy the following conditions.

2.   The burning number of the single tail $Q$ graph

In this section, we determine the burning number of the single tail $Q$ graphs $Q_{v}(s, t)$ and confirm the Bonato's conjecture. Further more, we characterize the single tail $Q$ graph by the burning number. Now we give some useful lemmas.

Lemma 2.1. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with order $n$, we have that $\lceil \sqrt{n}-1 \thinspace\rceil \leq b(G)\leq \lceil \sqrt{n} \thinspace\thinspace\rceil$.

Proof. Since $G$ has a hamiltonian path, by Theorem 1.1, the upper bound is clear. Let $v$ be the 3-degree vertex and $(x_1, x_2, \ldots, x_k)$ be an optimal burning sequence of $G$. Let $T_i$ denote the derived subtree with the root $x_i$ and a height that does not exceed $k-i$ in $G$. If no $T_i$ is spider, then $|N_{k-i}[x_i]|\leq 2(k-i)+1$ for $1\leq i\leq k$. Thus, we have $\sum_{i = 1}^k (2(k-i)+1) = k^{2}\geq n$, so $b(G) = k\geq \lceil \sqrt{n}\thinspace\thinspace\rceil$. If there exist a root subtree, named $T_1$, is the spider $S_{v}(a_{1}, a_{2}, a_{3})$ for $d(v, x_1) = l$. Then, $N_{k-1}[x_1]\leq 3(k-1)+1-l$. Combine this with the fact $|N_{k-i}[x_i]|\leq 2(k-i)+1$ for $2\leq i\leq k$, we have

Considering $k^2+k-1-l\geq n$ and $l\geq 0$, gives us $k\geq (n+5/4)^{1/2}-1/2\geq \lceil\sqrt{n}-1\thinspace\rceil$. This completes the proof. □

Lemma 2.2. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with $b(G) = k$. Then, $|V(G)|\leq k^2+k-1$.

Proof. Suppose $v$ is 3-degree vertex of $G$ and $(x_1, x_2, \ldots, x_k)$ is an optimal burning sequence of $G$. In order to let $G$ contain as many vertices as possible, the following conditions must holds:

(1) $x_1 = v$;

(2) $\bigcup{_{i = 1}^{k}}N_{k-i}[x_i] = V(G)$;

(3) $N_{k-i}[x_i]\cap N_{k-j}[x_j] = \emptyset$ for $1\leq i\neq j\leq k$.

Consider $d(x_i) = 2$ for $2\leq i\leq k$, so $|N_{k-i}[x_i]| = 2k-2i+1$. Combine $|N_{k-1}[v]| = 3k-2$, the maximum number of $|V(G)|$ is $\Sigma{_{i = 1}^k}|N_{k-i}[x_i]|$

□

By Lemma 2.1 and 2.2, we get the following corollaries.

Corollary 2.3. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with order $k^2+r$ for $1\leq r\leq2k+1$. Then, $k\leq b(G)\leq k+1$.

Corollary 2.4. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with order $k^2+r$ for $k\leq r\leq2k+1$. Then, $b(G) = k+1$.

The following we determine the exact value of the burning number of single tail $Q$ graph $b(Q_{v}(s, t))$ with order $k^2+r$ for $1\leq r\leq k-1$.

Lemma 2.5. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with order $k^2+r$ for $1\leq r\leq k-1$. If $s\geq k^2$ or $t\geq k^2$, then $b(G) = k+1$.

Proof. When $s\geq k^{2}$, consider $C_{s+1}$ is an isometric subgraph of $G$ with $|V(C_{s+1})|\geq k^2+1$. Then, by Theorem 1.1, $b(C_{s+1}) = \lceil\sqrt{|V(C_{s+1})|}\thinspace\thinspace\rceil\geq k+1$. Further more, we find that for any vertex $x\in V(G)\setminus V(C_{s+1})$ and any positive integer $r$, $N_r[x]\cap V(C_{s+1})\subseteq N{_r^{C_{s+1}}[v]}$. By Proposition 1.7 and Corollary 2.3, we get $k+1\leq b(C_{s+1})\leq b(G)\leq k+1$. So, $b(G) = k+1$. Similarly, since $P_{t+1}$ is an isometric subgraph of $G$ with $t\geq k^2$, we can show that $b(G) = k+1$. □

Lemma 2.6. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with order $k^2+k-1$. Then,

Proof. First, consider the case for $2\leq s\leq 2k-3$. Since $d(G) = \lceil\frac{s}{2}\rceil+t = \lceil\frac{s}{2}\rceil +k^2+k-1-s-1 = k^2+k-1-\lceil\frac{s+1}{2}\rceil\geq k^2+k-1-(k-1) = k^2$, by Proposition 1.6 and Corollary 2.3, we have $b(G) = k+1$. For the case $s = k^2-3$ or $2k$, we get $b(G) = k+1$. In fact, if not, assume $b(G) = k$. Then, by Lemma 2.2, we have $x_1 = v$. Let $H = G-N_{k-1}[v]$, then $b(H) = k-1$. However, notice $H = P_{s^{'}}\cup P_{t^{'}}$ with $s^{'} = s-(2k-2) = k^2-2k-1$ or 2, $t^{'} = t-(k-1) = 2$ or $k^2-2k-1$, by Proposition 1.8, we have $b(H) = k$, which contradicts to $b(H) = k-1$. So, we get $b(G) = k+1$.

Second, consider the case for $2k-2\leq s\leq k^2-1$ and let $x_1 = v$, and $H = G-N_{k-1}[v]$. Then, we have $H = P_{s^{'}}\cup P_{t^{'}}$ with $s^{'} = s-(2k-2)$ and $t^{'} = t-(k-1)$. Further more, notice that $s^{'}+t^{'} = k^2-2k+1$ and $s^{'}\neq k^2-2k-1$ or 2, so we have $t^{'}\neq 2$ or $k^2-2k-1$. Then, by Proposition 1.8, we get $b(H) = k-1$ and $b(G)\leq 1+b(H) = k$. Combine this with Corollary 2.3, and we get $b(G) = k$. □

Lemma 2.7. Let $G$ be single tail $Q$ graph with order $k^2+r$ for $1\leq r\leq k-2$. If $2\leq s\leq 2k-3$, then

Proof. First consider the case for $\lfloor s/2 \rfloor < r$. Since $d(G) = \lceil\frac{s}{2}\rceil+t = k^2+r-s-1+\lceil\frac{s}{2}\rceil = k^2+r-\lfloor s/2 \rfloor-1 > k^2-1$, $d(G)\geq k^2$. By Proposition 1.6 and Corollary 2.3, we have $b(G)\geq \lceil\sqrt{d(G)+1} \thinspace\thinspace\rceil = k+1$ and thus $b(G) = k+1$. Now consider the case for $\lfloor s/2 \rfloor\geq r$.

If $s$ is odd, let $(s-1)/2 = s^{'}$ and $x_1 = u\in V(P_{t+1})$ such that $d(v, u) = k-s^{'}-2$. Then, $V(C_{s+1})\subseteq N_{k-1}[u]$ and thus $G\setminus N_{k-1}[u] = P_{t^{'}}$ with $t^{'} = k^2+r-(2s^{'}+1)-(d(u, v)+1)-(k-1) = k^2+r-s^{'}-2k+1\leq k^2+r-r-2k+1 = (k-1)^2$. So, we have $b(P_{t^{'}}) = \lceil \sqrt {t^{'}}\thinspace\thinspace\rceil\leq k-1$. Thus, $b(G)\leq 1+ b(P_{t^{'}})\leq k$. Combine this with Corollary 2.3 and we get $b(G) = k$. If $s$ is even, let $s/2 = s^{'}$ and $x_1 = u\in V(P_{t+1})$ such that $d(v, u) = k-s^{'}-1$. Then, $V(C_{s+1})\subseteq N_{k-1}[u]$. Similarly, since $G\setminus N_{k-1}[u] = P_{t^{'}}$ with $t^{'} = k^2+r-2s^{'}-(d(u, v)+1)-(k-1) = k^2+r-s^{'}-2k+1\leq k^2+r-r-2k+1 = (k-1)^2$, we have $b(P_{t^{'}})\leq\lceil \sqrt {t^{'}}\thinspace\thinspace\rceil\leq k-1$ and thus $b(G)\leq k$. So $b(G) = k$. □

Lemma 2.8. Let $G$ be single tail $Q$ graph with order $k^2+r$ for $1\leq r\leq k-2$. If $2k-2\leq s \leq k^2-1$, then $b(G) = k$.

Proof. Let $x_1 = v$ and $H = G-N_{k-1}[v]$. If $t\geq k$, denote $t^{'} = t-(k-1)$, $s^{'} = s-(2k-2)$. Then, $H = P_{s^{'}}\cup P_{t^{'}}$ with $s^{'}+t^{'} = k^2+r-1-3(k-1)\leq k^2-2k < (k-1)^2$. By Proposition 1.8, we have that $b(H)\leq k-1$. Thus, $b(G)\leq k$. If $t\leq k-1$, $V(P_{t+1})\subseteq N_{k-1}(v)$ and $H = P_{s^{'}}$ with $s^{'} = s-(2k-2)$. Note that $s \leq k^2-1$, so $s^{'} \leq (k-1)^2$. Thus, $b(H)\leq k-1$. So, $b(G)\leq k$. □

To summarize the above discussion, we get following results.

Theorem 2.9. Let $G = Q_{v}(s, t)$ be a single tail $Q$ graph with order $k^2+r$ with $1\leq r\leq 2k+1$. Then,

3.   Burning number of the double tails $Q$ graph

In this section, we determine the burning number of the double tails $Q$ graph $G = Q_v(s, t_1, t_2)$ and confirm the Bonato's conjecture. Further more, we characterize the double tails $Q$ graph by the burning number. First, we give some lemmas.

Lemma 3.1. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $k^2+r$ with $1\leq r \leq 2k+1$. Then, $k\leq b(G)\leq k+1$.

Proof. Notice that $S_{v}(s, t_1, t_2)$ is a spanning tree of $G$. Then, by Propositions 1.3 and 1.4, we get $b(G)\leq b(S_{v}(s, t_1, t_2))\leq \lceil\sqrt{k^2+r}\thinspace\thinspace\rceil = k+1$. Now we show $b(G)\geq k$. Let $(x_1, x_2, \ldots, x_p)$ be an optimal burning sequence of $G$, $T_i(1\leq i\leq p)$ be the derived subtrees with the root $x_i$, and the height of $T_i$ be less than or equal to $p-i$. If there is no spider in $T_i(1\leq i\leq p)$, then $|N_{p-i}[x_i]|\leq 2(p-i)+1$ for $1\leq i\leq p$. Thus, $\sum_{i = 1}^p (2(p-i)+1) = p^{2}\geq k^2+r$ and $b(G) = p\geq \lceil \sqrt{k^2+r}\thinspace\thinspace\rceil = k+1 > k$. If there exist a spider in $T_i(1\leq i\leq p)$, without loss generality, assume $T_1$ is a spider. Suppose $T_1$ is three-arms spider $S_{v}(a_{1}, a_{2}, a_{3})$ such that $d(v, x_1) = l$. Then, $N_{p-1}[x_1]\leq 3(p-1)+1-l$. Similar to Lemma 2.1, we have $b(G) = p\geq \lceil \sqrt{k^2+r}-1\thinspace\rceil\geq k$. Suppose $T_1$ is a four-arms spider $S_v(a_1, a_2, a_3, a_4)$ such that $d(v, x_1) = m$. Then, we have $|N_{p-1}[x_1]|\leq 4(p-1)+1-2m$. Considering $|N_{p-i}[x_i]|\leq2(p-i)+1$ for $2\leq i\leq p$, we get

Considering $\bigcup{_{i = 1}^{p}}N_{p-i}[x_i] = V(G)$, we have $p^2+2p-2\geq k^2+r$. Thus, $p\geq \lceil\sqrt{k^2+r+3}\thinspace\thinspace\rceil-1\geq k$. □

Clearly, by Lemma 3.1, the burning number of double tails $Q$ graph $Q_v(s, t_1, t_2)$ with order $k^2+r$ for $1\leq r\leq2k+1$ is either $k+1$ or $k$. Further more, by the proof, we know that the order of $Q_v(s, t_1, t_2)$ with the burning number $k$ is not more than $k^2-2k+2$.

Claim 3.2. Let $S_{v}(a_1, a_2, \ldots, a_{\Delta})$ be a spider and $G$ be a path-forest. If $H = S_{v}(a_1, a_2, \ldots, a_{\Delta})\cup G$ and $b(H) = p$, then $|V(H)|\leq (p-1)^2+\Delta(p-1)+1$.

Lemma 3.3. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$ for $r\geq 2p-1$. Then, $b(G) = p+1$.

Proof. Notice that every spanning tree of $G$ is a union of spider and path-forest and $|V(G)| = p^2+r\geq p^2+2p-1 = (p-1)^2+4(p-1)+2$. Thus, by Claim 3.2, have $b(G) = p+1$. □

Lemma 3.4. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$ for $1\leq r \leq 2p-2$. If $s\geq p^2$ or $t = t_1+t_2\geq p^2$ or $t_1+\lceil\frac{s}{2}\rceil\geq p^2$, then $b(G) = p+1$.

Proof. Clearly, $C_{s+1}$ is an isometric subgraph of $G$. If $s\geq p^2$, then $|V(C_{s+1})|\geq p^2+1$. By Theorem 1.1 we have $b(C_{s+1}) = \lceil\sqrt{|V(C_{s+1})|}\thinspace\thinspace\rceil\geq p+1$. Further more, for any vertex $x\in V(G)\setminus C_{s+1}$ and positive integer $r$, we have $N_r[x]\cap V(C_{s+1})\subseteq N{_r^{C_{s+1}}[v]}$. By Proposition 1.7 and Corollary 2.1, we get $p+1\leq b(C_{s+1})\leq b(G)\leq p+1$. So, $b(G) = p+1$. Similarly, notice that $P_{t+1}, Q_{v}(s, t_1)$ are also isometric subgraphs of $G$. Consider $t\geq p^2$ and $t_1+\lceil\frac{s}{2}\rceil\geq p^2$. Then, by Proposition 1.7 and Corollary 2.1, we get $p+1\leq b(P_{t+1})\leq b(G)\leq p+1$ and $p+1\leq b(Q_{v}(s, t_1))\leq b(G)\leq p+1$. Thus, $b(G) = p+1$. □

Now we go on proposing claims.

Claim 3.5. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$ for $2p-2m-1\leq r\leq 2p-2m$ and $m\leq p-1$. If $b(G) = p$, then there exists one $i\in \{1, 2, \ldots, m\}$ such that $x_i\in N_{m-i}[v]$.

Proof. Suppose $(x_1, x_2, \ldots, x_p)$ is an optimal burning sequence of $G$ with order $p^2+r$ for $2p-2m-1\leq r\leq 2p-2m$ and $m\leq p-1$. Assume that all $x_i\notin N_{m-i}[v]$ for $i = 1, 2, \ldots, m$. Let $H$ be the subgraph of $G$ which induced by $N_{p-1}[x_1]\cup N_{p-2}[x_2]\cup\ldots\cup N_{p-m}[x_m]$. Now we show $b(G\setminus H) > p-m$, which implies that $b(G) > p$. This contradicts to $b(G) = p$.

If $v\in H$, suppose $v\in N_{p-j}[x_j]$ for $j\in\{1, 2, \ldots, m\}$, combine $x_j\notin N_{m-j}[v]$ we have $|N_{p-j}[x_j]|\leq 4(p-j)-2(m-j+1)+1 = 4p-2m-2j-1$. Consider $|N_{p-i}[x_i]|\leq 2(p-i)+1$ for $i\neq j$, we get

Thus, $|V(G \setminus H)|\geq (p-m)^2+1$. Considering that $G\setminus H$ is a path forest, then $b(G\setminus H) > p-m$, a contradiction.

If $v\notin H$, $|N_{p-i}[x_i]|\leq 2(p-i)+1$ for $i\in\{1, 2, \ldots, m\}$. Thus, $|V(G\setminus H)|\geq p^2+2p-(2m+1)-\sum_{i = 1}^{m}(2p-2i+1) = (p-m)^2+2(p-m)-1 = (p-m-1)^{2}+4(p-m-1)+2$. By Claim 3.2, we have that $b(G\setminus H) > p-m$, a contradiction. □

Claim 3.6. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+2p-2$. If $b(G) = p$, then $2p-2\leq s\leq p^2-1$, $p-1\leq t_2\leq t_1$, $t_1+t_2\leq p^2-1$, and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$.

Proof. Suppose $(x_1, x_2, \ldots, x_p)$ is an optimal burning sequence of $G$. Then, by Lemma 3.4, the upper bounds of $s, t_1+t_2$ and $t_1+\lceil\frac{s}{2}\rceil$ are clear. Here we only show the lower bound. Consider $r = 2p-2$ and $b(G) = p$, and then by Claim 3.5, we know that $x_1 = v$. Now assume that $s\leq 2p-3$ or $t_2\leq t_1\leq p-2$. Then, $|N_{p-1}[v]|\leq 4p-4$ and thus $|V(G\setminus N_{p-1}[v])|\geq p^2-2p+2$. Consider that $G\setminus N_{p-1}[v]$ is path forests. By Proposition 1.9, we get $b(G\setminus N_{p-1}[v])\geq p$ and thus $b(G)\geq p+1$, a contradiction. □

Lemma 3.7. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$ for $2p-3\leq r\leq 2p-2$. If $2p-2\leq s\leq p^2-1$, $p-1\leq t_2\leq t_1$, $t_1+t_2\leq p^2-1$, and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$, then

where $s^{'} = s-(2p-2), t_1^{'} = t_1-(p-1), t_2^{'} = t_2-(p-1)$.

Proof. Suppose $s^{'} = s-(2p-2), t_1^{'} = t_1-(p-1), t_2^{'} = t_2-(p-1)$ and we distinguish cases to complete the proof.

Case 1. $s^{'}t_2^{'}\neq 0$

If $(s^{'}, t_{1}^{'}, t_{2}^{'})\notin J^{1}\cup J^{2}\cup J^{3}\cup J^{4}\cup J^{5}$, we let $x_1 = v$ and $H = G-N_{p-1}[x_1]$. Notice that $|N_{p-1}[x_1]| = 4p-3$ and $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$. Then, $p^{2}-2p\leq |H|\leq p^{2}-2p+1$. By Proposition 1.9, we have $b(H) = p-1$. Thus, $b(G)\leq b(H)+1 = p$. Combining this with Lemma 3.1, we get $b(G) = p$. If $(s^{'}, t_{1}^{'}, t_{2}^{'})\in J^{1}\cup J^{2}\cup J^{3}\cup J^{4}\cup J^{5}$. Assume $b(G) = p$. Then, by Claim 3.5, we have $x_1 = v$. Let $H = G-N_{p-1}[x_1]$. Then, $b(H) = p-1$. Notice that $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$. Therefore, by Proposition 1.9, we have $b(H) = p$, a contradiction. Thus, $b(G) = p+1$.

Case 2. $s^{'}t_2^{'} = 0$

If $max\{s^{'}, t_{1}^{'}\}\neq p^{2}-2p-1$ or $r\neq 2p-2$, let $x_1 = v$ and $H = G-N_{p-1}[x_1]$. Consider $|N_{p-1}[x_1]| = 4p-3$ and $H$ is 2-path forests. Thus, by Proposition 1.8, we have $b(H) = p-1$. Then, $b(G)\leq b(H)+1 = p$. Combining this with Lemma 3.1, we have $b(G) = p$. If $\max\{s^{'}, t_{1}^{'}\} = p^{2}-2p-1$ and $r = 2p-2$, assume $b(G) = p$ rather than $p+1$, by Claim 3.5 we have $x_1 = v$ and thus $b(H) = p-1$ for $H = G-N_{p-1}[x_1]$. However, notice $r = 2p-2$, we have $|V(H)| = p^{2}-2p+1$ and $H = P_{2}\cup P_{p^{2}-2p-1}$. By Proposition 1.8, we have $b(H) = p$, a contradiction. Thus, $b(G) = p+1$. □

Lemma 3.8. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+2p-4$. If $2p-2\leq s\leq p^2-1$, $p-1\leq t_2\leq t_1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$. Then,

Proof. Clearly, $t_1+t_2+s+1 = p^2+2p-4$. Now we distinguish cases to discuss.

Case 1. $s\neq 2p$.

Subcase 1.1. $t_2\neq p+1$.

Let $x_1 = v$ and $H = G\setminus N_{p-1}[v]$. Then, $|V(H)| = (p-1)^2-2$ and $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$ with $s^{'} = s-(2p-2)$, $t_{1}^{'} = t_1-(p-1)$ and $t_{2}^{'} = t_2-(p-1)\neq 2$. Let $y = \min\{s^{'}, t_{1}^{'}\}$, and then it is clear that $(y, t_{2}^{'})\notin D_{1}\cup D_{2}$. Then, by Proposition 1.9 and Lemma 3.1, we have $b(H) = p-1$ and thus $b(G) = p$.

Subcase 1.2. $t_2 = p+1$ but $t_1\neq p+2$.

If $t_1 = p+1$, let $x_1\in V(P_{t_2})$ with $d(x_1, v) = 1$ and $H = G\setminus N_{p-1}[x_1]$, $|V(H)| = (p-1)^2$ and $H = P_{s^{'}}\cup P_{3}\cup P_{1}$ with $s^{'} = s-(2p-4)$. Notice $|V(H)| = (p-1)^2 > 4$, we have $p\geq 4$ and thus $s^{'}\geq 5$. Clearly, $(s^{'}, 3, 1)\notin J^1\cup J^2\cup J^3\cup J^4\cup J^5$. By Lemma 3.1, we have $b(H) = p-1$ and thus $b(G) = p$.

Now consider the case for $t_{1}\geq p+3$. If $s = 2p+1$, then $t_{1} = p^2-p-7$. Let $x_1\in V(P_{t_{2}})$ with $d(x_1, v) = 1$. Let $H = G\setminus N_{p-1}[x_1]$. Then, $|V(H)| = (p-1)^2$ and $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$ with $s^{'} = s-2(p-2) = 5$, $t_{1}^{'} = t_1-(p-2)\geq 5$ and $t_{2}^{'} = t_2-p = 1$. Notice $(1, 5)\in\bigcup_{i = 1}^{4}D_i$. Hence $(s^{'}, t_{1}^{'}, t_{2}^{'})\notin J^1\cup J^2\cup J^3\cup J^4\cup J^5$, and by Proposition 1.9 and Lemma 3.1, we have $b(H) = p-1$. Thus $b(G) = p$. If $s\neq 2p+1$, let $x_1 = v$ and $H = G\setminus N_{p-1}[v]$, and consider $|N_{p-1}[x_1]| = 4p-3$. Then, $|V(H)| = (p-1)^2-2$. Let $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$ with $s^{'} = s-(2p-2)\neq 2, 3$, $t_{1}^{'} = t_1-(p-1)\geq 4$, $t_{2}^{'} = t_2-(p-1) = 2$ and $y = min\{s^{'}, t_{1}^{'}\}$. Notice $(y, t_{2}^{'})\notin D_{1}\cup D_{2}$, so by Proposition 1.9 and Lemma 3.1, we have $b(H) = p-1$ and thus $b(G) = p$.

Subcase 1.3. $t_1 = p+2$ and $t_2 = p+1$.

In this case we give a proof to show $b(G) = p+1$ by contradiction. Assuming that $b(G) = p$, by Claim 3.5, we have that $x_1\in N_{1}[v]$ or $x_2 = v$.

If $x_1\in N_{1}[v]$, let $H = G\setminus N_{p-1}[x_1]$. Then, $b(H) = p-1$. In fact, we can prove $b(H) = p$ to derive contractions. If $x_1 = v$, then $H = P_{s^{'}}\cup P_{2}\cup P_{3}$ with $|V(H)| = (p-1)^2-2$ and $s^{'} = s-2(p-1)$. Notice $|V(H)|\geq 5$, we have $p\geq 4$ and $s = p^2+2p-4-(p+2)-(p+1)-1 = p^2-8$. Thus, $s^{'} = p^{2}-8-2(p-1)\geq 2$, by Proposition 1.9, we have $b(H) = p$.

If $x_1\in V(C_{s+1})$ with $d(x_1, v) = 1$, then $H = P_{s^{'}}\cup P_{4}\cup P_{3}$ with $|V(H)| = (p-1)^2$ and $s^{'} = s-2(p-1)$. Considering $|V(H)|\geq 7$, we have $p\geq 4$, then $s^{'}\geq 2$. Let $y = min\{s^{'}, 4\}$ and consider $\{y, 3\}\in D_{1}\cup D_{2}\cup D_{3}\cup D_{4}$. Then, by Proposition 1.9, we have $b(H) = p$. If $x_1\in V(P_{t_1})$ with $d(x_1, v) = 1$, then $H = P_{s^{'}}\cup P_{2}\cup P_{3}$ with $|V(H)| = (p-1)^2$ and $s^{'} = s-2(p-2)\geq 2$. By Proposition 1.9, we have $b(H) = p$. Similarly, if $x_1\in V(P_{t_2})$ with $d(x_1, v) = 1$, then we also can prove $b(H) = p$.

If $x_2 = v$, let $H = G\setminus N_{p-2}[x_2]\setminus N_{p-1}[x_1]$, and considering $|G\setminus N_{p-2}[x_2]| = p^2-2p+3$, we get $b(H) = p-2$. Now we show $b(H) = p-1$ to derive contractions. Consider $|N_{p-1}[x_1]| = 2(p-1)+1$ and $|G\setminus N_{p-2}[x_2]| = p^2-2p+3\geq t_1-(p-2)+t_2-(p-2) = 7$, such that we have $p\geq 4$. Then, $|N_{p-1}[x_1]|\geq 7$. So, $x_1\in V(C_{s+1})$ and $H = P_{s^{'}}\cup P_{4}\cup P_{3}$ with $|V(H)| = (p-2)^2$ and $s^{'}\geq 2$ for $(p-2)^{2} > 7$. By Lemma 3.1 and Proposition 1.9, we have $b(H) = p-1$.

Case 2. $s = 2p$.

Subcase 2.1. $t_2\in\{p+1, p+2\}$.

Similarly, we have a contradiction to show $b(G) = p+1$. Assume $b(G) = p$, by Claim 3.5, we have that $x_1\in N_{1}[v]$ or $x_2 = v$. Let $H = G\setminus N_{p-1}[x_1]$ or $G\setminus N_{p-2}[x_2]\setminus N_{p-1}[x_1]$. Then, $b(H) = p-1$ or $p-2$. Now we show $b(H) = p$ or $p-1$ to derive contractions, respectively.

If $x_1 = v$, then $|V(H)| = (p-1)^2-2$ and $H = P_{2}\cup P_{2}\cup P_{t_{1}^{'}}$ or $P_{2}\cup P_{3}\cup P_{t_{1}^{'}}$ with $t_{1}^{'} = t_{1}-(p-1)\geq 2$. By Proposition 1.9, $b(H) = p$. If $x_1\in V(C_{s+1})$ with $d(x_1, v) = 1$, then $|N_{p-1}[x_1]| = 4p-5$, $|V(H)| = (p-1)^2$ and $H = P_{2}\cup P_{3}\cup P_{t_{1}^{'}}$ or $P_{2}\cup P_{4}\cup P_{t_{1}^{'}}$ with $t_{1}^{'} = t_{1}^{'}-(p-2)\geq 3$. By Proposition 1.9, we also get $b(H) = p$, contradiction. Similarly, we can show $b(H) = p$ for other cases $x_1\in V(P_{t_1})$ with $d(x_1, v) = 1$ and $x_1\in V(P_{t_2})$ with $d(x_1, v) = 1$, details are omitted.

If $x_2 = v$, let $H = G\setminus N_{p-2}[x_2]\setminus N_{p-1}[x_1]$, and consider $b(G) = p$. Then, $b(H) = p-2$. Clearly, $|V(H)|\geq(p-2)^2$. Further more, we get $|V(H)| = (p-2)^2$. If $|V(H)| > (p-2)^2$, then $b(H)\geq p-1$, which contradicts to $b(H) = p-2$. Since $t_{2}-(p-2)\leq 4$, $s-2(p-2) = 4$, we have $x_1\in V(P_{t_{1}})$. Consider $P_{4}\cup P_{3}$ or $P_{4}\cup P_{4}\subseteq H$, such that $p\geq 5$. By Proposition 1.9, we have $b(H) = p-1$, a contradiction.

Subcase 2.2. $t_2\notin \{p+1, p+2\}$.

In this case, we let $x_1 = v$ and $H = G\setminus N_{p-1}[x_1]$. Clearly, $V(H) = (p-1)^2-2$ and $H = P_{t_1^{'}}\cup P_{t_2^{'}}\cup P_{2}$, satisfying $t_1^{'} = t_1-(p-1)$, $t_2^{'} = t_2-(p-1)\notin\{ 2, 3\}$. By Proposition 1.9 and Lemma 3.1, we have $b(H) = p-1$ and thus $b(G) = p$. □

Lemma 3.9. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+2p-5$. If $2p-2\leq s\leq p^2-1$, $p-1\leq t_2\leq t_1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$, then $b(G) = p$.

Proof. If $t_2 = p+1$, we let $x_1\in V(P_{t_2})$ such that $d(v, x_1) = 1$ and $H = G\setminus N_{p-1}[x_1]$. Consider $|V(H)| = (p-1)^2-1$ and $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{1}$ with $s^{'} = s-(2p-4)\geq 2$ and $t_{1}^{'} = t_1-(p-2)\geq 3$. Let $y = \min\{s^{'}, t_{1}^{'}\}$. Since $(y, 1)\notin D_{1}\cup D_{2}\cup D_{3}$, by Proposition 1.9 and Lemma 3.1, we get $b(H) = p-1$ and thus $b(G) = p$.

If $t_2\geq p+2$ or $p-1\leq t_2\leq p$, let $x_1 = v$ and $H = G\setminus N_{p-1}[v]$. Then, $|V(H)| = (p-1)^2-3$ and $H = P_{s^{'}}\cup P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$ with $s^{'} = s-(2p-2)$, $t_{1}^{'} = t_1-(p-1)$ and $t_2^{'} = t_2-(p-1)\neq 2$. When $s^{'}t_{2}^{'} = 0$, by Proposition 1.8, we get $b(H) = p-1$. If $s^{'}t_{2}^{'}\neq 0$, let $y = \min\{s^{'}, t_1^{'}\}$ and notice $(y, t_{2}^{'})\notin D_{1}$. Then, by Proposition 1.9 and Lemma 3.1, we have $b(H) = p-1$ and thus $b(G) = p$. □

Lemma 3.10. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$. If $r\leq 2p-6$, $2p-2\leq s\leq p^2-1$, $p-1\leq t_2\leq t_1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$, then $b(G) = p$.

Proof. Let $x_1 = v$ and $H = G\setminus N_{p-1}[v]$ such that $b(H)\leq p-1$. Clearly, since $|N_{p-1}[v]| = 4p-3$ and $H = P_{s^{'}}\cup P_{t_1^{'}}\cup P_{t_2^{'}}$ for $s^{'} = s-(2p-2)$, $t_{1}^{'} = t_1-(p-1)$ and $t_2^{'} = t_2-(p-1)$, $|V(H)|\leq (p-1)^2-4$. By Propositions 1.8 and 1.9, we get $b(H)\leq p-1$. This completes the proof. □

By Lemmas 3.7–3.10, we obtain the burning number of $Q_{v}(s, t_{1}, t_{2})$ with order $p^2+r$ for $1\leq r\leq 2p-3$ when $2p-2\leq s\leq p^2-1$, $p-1\leq t_2\leq t_1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$. Now, we get following results.

Theorem 3.11. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$ for $1\leq r\leq 2p+1$. If $r\geq 2p-1$ or $1\leq r\leq 2p-2$ and $s\geq p^2$ or $1\leq r\leq 2p-2$ and $t_1+t_2\geq p^2$ or $1\leq r\leq 2p-2$ and $t_1+\lceil\frac{s}{2}\rceil\geq p^2$, then $b(G) = p+1$.

Following Theorem 3.11, we consider the case for $2p-2\leq s\leq p^2-1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$.

Theorem 3.12. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$ for $1\leq r\leq2p-2$ and $2p-2\leq s\leq p^2-1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$. If $s^{'} = s-(2p-2), t_1^{'} = t_1-(p-1), t_2^{'} = t_2-(p-1)$, then $b(G) = p$.

At the end of this section, we discuss cases for $s\leq 2p-3$, $t_2\leq p-2$ and $t_1\leq p-2$, respectively.

Theorem 3.13. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$. If $1\leq r\leq 2p-3$, $2p-2\leq s\leq p^2-1$, $t_2\leq p-2$, $t_1\geq p-1$, $t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$, then

Proof. Clearly, $G^{'} = Q_{v}(s, t_1)$ is an isometric subgraph of $G$ and for any $u\in V(G\setminus G^{'})$ and any position integer $r$, $N_{r}^{G}[u]\cap$ $V(G^{'})\subset N_{r}^{G^{'}}[v]$. Thus, by Proposition 1.7, we get $b(G^{'})\leq b(G)$.

First, consider the case for $r\geq p-1$ and $1\leq t_2\leq r-p$. Then, $|V(G^{'})| = n-t_2\geq p^2+p$. By Corollary 2.4, we know that $p+1 = b(G^{'})\leq b(G)$. Thus we get $b(G) = p+1$. If $r\geq p-1$, $t_2 = r-p+1$, then $|V(G^{'})| = p^2+p-1$. When $s\notin \{p^2-3, 2p\}$, by Lemma 2.6, we have $b(G^{'}) = p$. Further, by Lemma 2.2 we know that $x_1 = v$. Notice $t_2\leq p-2$, so $V(P_{t_2})\subset N_{p-1}[v]$ and thus we get $b(G) = p$. When $s\in \{p^2-3, 2p\}$, by Lemma 2.6, we have $b(G^{'}) = p+1$. Thus $b(G) = p+1$. Next, we consider two cases for $r\geq p-1$, $t_2\geq r-p+2$ and $r\leq p-2$. Notice that $|V(G^{'})|\leq p^2+p-2$ in these two cases. By Lemma 2.8, we know that $x_1 = v$ and $b(G^{'}) = p$. By combining this with $V(P_{t_2})\subset N_{p-1}[v]$ for $t_2\leq p-2$, we have $b(G) = p$. □

Theorem 3.14. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$. If $1\leq r\leq 2p-3$, $2p-2\leq s\leq p^2-1$, $t_1\leq p-2$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$, then $b(G) = p$.

Proof. Let $x_1 = v$. Then, it is clear that $V(P_{t+1})\subseteq N_{p-1}[v]$. Suppose $P_{s^{'}} = G\setminus N_{p-1}[x_1]$ with $s^{'} = s-(2p-2)\leq p^2-2p+1$. Then, by Theorem 1.1 we have $b(P_{s^{'}})\leq p-1$. Thus $b(G)\leq b(P_{s^{'}})+1\leq p$. By combining this with Lemma 3.1, we have $b(G) = p$. □

Theorem 3.15. Let $G = Q_v(s, t_1, t_2)$ be a double tails $Q$ graph with order $p^2+r$. If $1\leq r\leq 2p-3$, $s\leq 2p-3$, $t = t_1+t_2\leq p^2-1$ and $t_1+\lceil\frac{s}{2}\rceil\leq p^2-1$. Then,

Proof. Now we distinguish three cases to complete the proof.

Case 1. $t_2\leq \lceil\frac{s}{2}\rceil$.

Let $x_1\in V(P_{t_1+1})$ such that $d(x_1, v) = p-1-\lceil\frac{s}{2}\rceil$. Clearly, $V(C_{s+1})\subseteq N_{p-1}[x_1]$ and $V(P_{t_2})\subseteq N_{p-1}[x_1]$ for $t_2\leq \lceil\frac{s}{2}\rceil$. Thus $G\setminus N_{p-1}[x_1] = P_{t_{1}^{'}}$ with $t_{1}^{'} = t-t_2-d(x_1, v)-(p-1)-1\leq p^2-2p$, by Theorem 1.1 and Lemma 3.1 we have $b(P_{t_{1}^{'}})\leq p-1$. Thus $p\leq b(G)\leq b(P_{t_{1}^{'}})+1\leq p$ and we get $b(G) = p$.

Case 2. $t_2 > \lceil\frac{s}{2}\rceil$ but $t_{2}\neq \lceil\frac{s}{2}\rceil+2$ or $t\leq p^2-2$.

Let $x_1\in V(P_{t_1+1})$ such that $d(x_1, v) = p-1-\lceil\frac{s}{2}\rceil$, it is clear that $V(C_{s+1})\subseteq N_{p-1}[x_1]$ and $G\setminus N_{p-1}[x_1] = P_{t_1^{'}}\cup P_{t_2^{'}}$ with $t_{1}^{'} = t_{1}-d(x_{1}, v)-(p-1)$, $t_{2}^{'} = t_{2}+d(x_{1}, v)-(p-1)$. If $t_{2}\neq \lceil\frac{s}{2}\rceil+2$, then $t_{2}^{'}\neq 2$ and $t_{1}^{'}+ t_{2}^{'}\leq p^2-2p+1$, by Proposition 1.8, we have $b(P_{t_1^{'}}\cup P_{t_2^{'}}) = p-1$. Thus $b(G) = p$. If $t\leq p^2-2$, then $t_1^{'}+t_2^{'}\leq p^2-2p$. By Proposition 1.8, we know that $b(P_{t_{1}^{'}}\cup P_{t_{2}^{'}}) = p-1$. Combined with Lemma 3.1, we get $b(G) = p$.

Case 3. $t_2 = \lceil\frac{s}{2}\rceil+2$ and $t = p^2-1$.

If $s\leq 2p-4$, let $x_1\in V(P_{t_1})$ such that $d(x_1, v) = p-2-\lceil\frac{s}{2}\rceil$. Clearly $V(C_{s+1})\subset N_{p-1}[x_1]$ and $Q_{v}(s, t_1, t_2)\setminus N_{p-1}[x_1] = P_{t_{1}^{'}}\cup P_{t_{2}^{'}}$ with $t_1^{'} = t_1-d(x_1, v)-(p-1) = p^2-2p$ and $t_{2}^{'} = t_{2}+d(x_1, v)-(p-1) = 1$. By Proposition 1.8 and Lemma 3.1, we have $b(P_{t_{1}^{'}}\cup P_{t_{2}^{'}}) = p-1$ and thus $b(G) = p$.

If $s = 2p-3$, then $t_2 = p+1$ and we can show $b(G) = p+1$. If not, assume $b(G) = p$ and $(x_1, x_2, \ldots, x_p)$ is an optimal burning sequence for $G$. Notice $H = P_{t_1+t_2+1}$ is an isometric subgraph of $G$ and for any vertex $u\in V(G\setminus H)$ and any position integer $r$, $N^{G}_r[u]\cap V (H)\subset N_{r}^H[v]$. By Proposition 1.7, we get $b(H)\leq b(G) = p$. Consider $|V(H)| = p^2$, this means $\{x_1, x_2, \ldots, x_p\}\subset V(H)$ and $V(C_{s+1})\subset N_{p-i}[x_i]$ for some $i$. Further, by $r(C_{s+1}) = \lceil\frac{s}{2}\rceil = p-1$ we know $V(C_{s+1})\subset N_{p-1}[x_1]$ for $x_1 = v$, we find $G\setminus N_{p-1}[v] = P_{2}\cup P_{p^2-2p-1}$. By Proposition 1.8, we get $b(P_{2}\cup P_{p^2-2p-1}) = p$ and thus $b(G) = p+1$, a contradiction. Then, $b(G) = p+1$. □

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank anonymous reviewers for their valuable comments and suggests to improve the quality of the article. This work was supported by NSFC No.12371352 and Qinghai provincial basic research project No.2022-ZJ-753.

Conflict of interest

The authors declare no conflicts of interest.