Qiuye Zhu, Yinkui Li^*
Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China.
DOI: 10.4236/ojapps.2025.155080   PDF    HTML   XML   114 Downloads   691 Views   Citations

Abstract

Graph burning is a model for describing the spread of influence in social networks and the burning number is a parameter used to describe the speed of information spread. In 2016, Bonato proposed a graph burning conjecture: For any connected graph $G$ with order $n$ , the burning number $b\left(G\right)\le \lceil \sqrt{n}\rceil$ . In this paper, we confirm the burning conjecture for octopus graph and bicyclic graph.

Keywords

Graph Burning, Burning Number, Octopus Graph, Bicyclic Graph

Share and Cite:

1. Introduction

Graph burning is a model that describes the spread of social contagion on social networks such as Facebook or Twitter. We use Bondy and Murty [1] for the notation and terminology, burning process is defined as follows. Given a finite and simple graph $G$ , vertices may be either burned or unburned throughout the process. Initially, at time $t=0$ , all vertices are unburned. At each time $t\ge 1$ , one new unburned vertex is chosen to burn, if such a vertex is available, we call such a chosen vertex a fire source. If a vertex is burned, then it remains in that state until the end of the process. Once a vertex is burned at time $t$ , at time $t+1$ each of its unburned neighbors becomes burned. The process ends when all vertices of $G$ are burned.

Note that the burning process on $G$ may be highly dependent on the choice of fire sources, the strategic choice of sources is critical when minimizing the length of the process. In [2], Bonato introduced the burning number of graph $G$ , denoted by $b\left(G\right)$ , is the minimum steps to burn graph $G$ . The fire sources $x_1,\cdots ,x_k$ that are chosen over time on graph $G$ are referred to as a burning sequence $\left(x_1,\cdots ,x_k\right)$ of $G$ and call the shortest burning sequence optimal. Clearly, optimal burning sequences have length $b\left(G\right)$ .

In 2016, Bonato et al proposed the burning conjecture:

Conjecture 1.1 [3]. For a connected graph $G$ of order $n$ , $b\left(G\right)\le \lceil \sqrt{n}\rceil$ .

Later, the conjecture been comfirm for some graph classes, such as spiders [4], path forests [5], caterpillars [6] [7], theta graph [8], fence graph [9], generalized Petersen graph [10], the Cartesian product of paths [11], $Q$ graph [12], binary tree [13] and trees without degree-2 vertices [14].

Motivated by these, we put forward on the paths and circles. We first denote octopus graph $G$ which obtained from comet graph $C_{l_i,2}$ for $1\le i\le m$ by identifing the tail of $C_{l_i,2}$ at $v_0$ , clearly, $d\left(v_0\right)=m$ . All degree-3 vertices but $v_0$ denoted by $u_i$ , we call $C_{l_i,2}$ an arm of Octopus and $l_i$ is the length of arm $C_{l_i,2}$ (see Figure 1). Here the comet $C_{r,s}$ is a graph which obtained by the end of path $P_r$ with the center of star graph $K_{1,s}$ .

Figure 1. Octopus graph G.

Another class of graph named $t$ tail bicyclic graph. If $t=1$ , call single tail bicyclic graph which obtained by joining the center vertex of the bicyclic graphs with one vertex of the path $P_{a_1+1}$ denoted by $G_{v_0\left(g_1,g_2,a_1\right)}$ . If $t=2$ , call double tail bicyclic graph which obtained by joining the center vertex of the bicyclic graph with a vertex of path $P_{a_1+1}$ and path $P_{a_2+1}$ denoted by $G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ (see Figure 2). They all only have a vertex $v_0$ with $d\left(v_0\right)>2$ , without loss of generality, we suppose $g_1\ge g_2$ .

Figure 2. $t$ tail bicyclic graph $G_{v_0\left(g_1,g_2,a_1\right)}$ and $G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ ($t=1,2$ ).

In this paper, we first confirm the burning conjecture for these 3 kind of graphs, next we discuss the burning number of single tail bicyclic graph $G_{v_0\left(g_1,g_2,a_1\right)}$ and double tail bicyclic graph $G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ .

2. Primarilies

Lemma 2.1 [2] If $\left(x_1,x_2,\cdots ,x_k\right)$ is a sequence of nodes in a graph $G$ such that $N_{k-1}\left[x_1\right]\cup N_{k-2}\left[x_2\right]\cup \cdots \cup N_1\left[x_{k-1}\right]\cup N_0\left[x_k\right]=V\left(G\right)$ , then $b\left(G\right)\le k$ .

Lemma 2.2 [3] For a path $P_n$ or a cycle $C_n$ on $n$ nodes, we have $b\left(P_n\right)=b\left(C_n\right)\le \lceil \sqrt{n}\rceil$ .

Lemma 2.3 [3] For a graph $G$ , $b\left(G\right)=\min \left\{b\left(T\right):T\text{is}\text{a}\text{spanning}\text{tree}\text{of}G\right\}$ .

Lemma 2.4 [3] For any graph $G$ with radius $r$ and diameter $d$ , we have that $\lceil {\left(d+1\right)}^{\frac{1}{2}}\rceil \le b\left(G\right)\le r+1$ .

Lemma 2.5 [4] The burning number of a spider graph G of order n satisfies $b\left(G\right)\le \lceil \sqrt{n}\rceil$ .

Lemma 2.6 [4] If $G$ is a path-forest of order $n$ with $t\ge 1$ components, then $b\left(G\right)\le \lfloor \frac{n}{2}\rfloor +t$ .

Lemma 2.7 [5] Let $G=P_{a_1}\cup P_{a_2}$ with $a_1\ge a_2\ge 1$ and $J\left(t\right)=\left\{\left(t^2-2,2\right)\right\}$ for integer $t\ge 2$ . Then

$b\left(G\right)=\{\begin{array}{ll}\lceil \sqrt{a_1+a_2}\rceil +1,\hfill & \text{If}\left(a_1,a_2\right)\in J\left(t\right);\hfill \\ \lceil \sqrt{a_1+a_2}\rceil ,\hfill & \text{Otherwise}.\hfill \end{array}$

Lemma 2.8 [5] Let $G=P_{a_1}\cup P_{a_2}\cup P_{a_3}$ with $a_1\ge a_2\ge a_3\ge 1$ . Then

$b\left(G\right)=\{\begin{array}{ll}\lceil \sqrt{a_1+a_2+a_3}\rceil +1,\hfill & \text{If}\left(a_1,a_2,a_3\right)\in J^1\cup J^2\cup J^3\cup J^4\cup J^5;\hfill \\ \lceil \sqrt{a_1+a_2+a_3}\rceil ,\hfill & \text{Otherwise}.\hfill \end{array}$

Let $J^i$ for $1\le i\le 5$ satisfy the following conditions.

$D_1=\left\{\left(2,2\right)\right\},$

$D_2=\left\{\left(3,2\right)\right\},$

$D_3=\left\{\left(1,1\right),\left(3,3\right),\left(4,2\right),\left(5,5\right)\right\},$

$D_4=\left\{\left(2,1\right),\left(4,1\right),\left(4,3\right),\left(4,4\right),\left(6,1\right),\left(6,4\right),\left(6,5\right),\left(6,6\right),\left(7,7\right),\left(8,4\right),\left(8,6\right),\left(10,4\right)\right\},$

$\begin{array}{l}{D}_5=\{\left(11,10,4\right),\left(13,11,1\right),\left(11,11,3\right),\left(22,13,1\right),\left(19,13,4\right),\left(17,13,6\right),\left(15,13,8\right),\\ \left(13,13,10\right),\left(17,15,4\right),\left(15,15,6\right),\left(30,15,4\right),\left(28,15,6\right),\left(26,15,8\right),\left(19,15,15\right),\\ \left(28,17,4\right),\left(26,17,6\right),\left(17,17,15\right),\left(26,19,4\right),\left(43,17,4\right),\left(41,17,6\right),\left(30,17,17\right),\\ \left(41,19,4\right),\left(30,30,4\right),\left(58,19,4\right)\},\end{array}$

$J^1=\left\{\left(a_1,a_2,a_3\right):\left(a_2,a_3\right)\in D_1,a_1+a_2+a_3=t^2-3\text{for}\text{integert}\right\},$

$J^2=\left\{\left(a_1,a_2,a_3\right):\left(a_2,a_3\right)\in D_1\cup D_2,a_1+a_2+a_3=t^2-2\text{for}\text{integert}\right\},$

$J^3=\left\{\left(a_1,a_2,a_3\right):\left(a_2,a_3\right)\in {\displaystyle \underset{i=1}{\overset{3}{\cup }}{D}_i},a_1+a_2+a_3=t^2-1\text{for}\text{integert}\right\},$

$J^4=\left\{\left(a_1,a_2,a_3\right):a_3=2\text{or}\left(a_2,a_3\right)\in {\displaystyle \underset{i=1}{\overset{4}{\cup }}{D}_i},a_1+a_2+a_3=t^2\text{for}\text{integert}\right\},$

$J^5=D_5\cup \left\{11,11,2\right\}.$

3. Main Results

In this section, we first confirm the burning conjecture for octopus graph $G$ , single tail bicyclic graph $G_{v_0\left(g_1,g_2,a_1\right)}$ and double tail bicyclic graph $G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ .

Theorem 3.1 Let $G$ be a octopus graph with order $n$ . Then $b\left(G\right)\le \lceil \sqrt{n}\rceil$

Proof. Let $G$ be a octopus graph with order $n$ . Without loss of generality, suppose $n=q^2+p$ for $1\le p\le 2q+1$ . The neighbors of $v_0$ are $v_1,v_2,\cdots ,v_i$ respectively and the length of longest arm is $l$ . If $q=2$ , it’s clearly that $b\left(G\right)\le \lceil \sqrt{n}\rceil$ . Consider $q\ge 3$ , next we distinguish 3 cases to complete the proof.

Case 1 If $l\le q$ .

It’s clearly that radius of $G$ is $r\le q$ , by lemma 2.4, we have $b\left(G\right)\le \lceil \sqrt{n}\rceil$ .

Case 2 If $q+1\le l\le 2q-1$ .

Consider the structure of the arm, we will discuss two cases.

Subcase 2.1 The arms of $G$ have the same structure.

If each arm has the same length, then $G$ has $q$ arms of length $q+1$ . First we set the $x_1$ on $v_1$ , then $C_{l_1,2}\subseteq N_q\left[x_1\right]$ . We denoted the part of $G\backslash N_q\left[x_1\right]$ is $R=R_1\cup R_2\cup \cdots \cup R_{q-1}$ , clearly, the height of $R_i\left(1\le i\le q-1\right)$ is 2 and each $R_i$ contains $u_i$ . Now suppose $\left(x_2,x_3,\cdots ,x_q\right)$ is a burning sequence of $R$ and let $x_{i+1}=u_i$ for $1\le i\le q-1$ , then we have $V\left(G\right)\subseteq N_q\left[x_1\right]\cup N_{q-1}\left[x_2\right]\cup N_{q-2}\left[x_3\right]\cup \cdots \cup N_1\left[x_q\right]$ . By lemma 2.1, we have $b\left(G\right)\le \lceil \sqrt{n}\rceil =q+1$ .

Subcase 2.2 The arms of $G$ doesn’t have the same structure.

It’s clearly that $G$ doesn’t have $q$ arms of length $q+1$ . We set $x_1$ on $v_0$ , if $l_i\le q$ , then $C_{l_i,2}\subseteq N_q\left[x_1\right]$ . We denoted the part of $G\backslash N_q\left[x_1\right]$ is $R_1\cup R_2\cup \cdots \cup R_i\left(i\ge 1\right)$ . Since the arm of octopus $G$ has length at most $2q-1$ , then each $R_i$ has length and order at most $q-2$ and $q$ respectively. Next we discuss the burning number of $G$ by the number of $i$ compontent.

When $i\le \frac{q+1}{2}$ . We remove a pendant vertex to another pendant vertex such that $R_i$ become a path $P_i$ , $P=P_1\cup P_2\cup \cdots \cup P_i\left(i\ge 1\right)$ , it’s clearly that $b\left(R\right)\le b\left(P\right)$ . Next we denoted $w_k$ is ssthe center of $P_k$ , for each $k=1,2,\cdots ,i$ , we can by neighborhood $N_{q-k}\left[w_k\right]$ cover the $P_k$ . since $2\left(q-k\right)+1\ge 2\cdot \frac{q+1}{2}+1=q$ , thus $b\left(R\right)\le b\left(P\right)\le q$ . By lemma 2.1, we have $b\left(G\right)\le \lceil \sqrt{n}\rceil =q+1$ .

When $i=\frac{q+2}{2}$ , $q$ is even. For each $k=1,2,\cdots ,i-1$ , every $R_k$ can be covered by $N_{q-k}\left[w_k\right]$ . For $R_i$ , it has the lenght at most $q-2$ , if $R_i$ only have 2 isolated vertex, we set $w_i$ at $u_i$ , otherwise $w_i$ is the center of $R_i$ , $2\left(q-i\right)=2\left(q-\frac{q+2}{2}\right)=q-2$ , thus $R_i\subseteq N_{q-i}\left[w_i\right]$ . By lemma 2.1, we have $b\left(G\right)\le \lceil \sqrt{n}\rceil =q+1$ .

When $i\ge \lfloor \frac{q+4}{2}\rfloor$ . Since $l\ge q+1$ and $G$ doesn’t have $q$ arms of length $q+1$ , then there must exist an arm $C_{l_i,2}$ with the length $\left|l_i\right|\le q$ . $C_{l_i,2}-\left\{v_0\right\}$ contain at least 3 vertices, then $N_q\left[x_1\right]$ contains at least $iq+4$ vertices, thus $\left|R\right|\le n-iq-1-3\le q\left(q+2-i\right)-3$ . If $i=q+1$ , then $\left|R\right|\le q-3\le i=q+1$ , the number of vertices is smaller than the number of branches, a contradiction. If $i=q$ , then $\left|R\right|\le 2q-3\ge i=q\left(q\ge 3\right)$ , a satisfaction.

So we only consider $\lfloor \frac{q+4}{2}\rfloor \le i\le q$ , removing a pendant vertex to another pendant vertex doesn’t change the number of vertices of $R$ , thus $V\left(R\right)=V\left(P\right)$ . By $b\left(R\right)\le b\left(P\right)$ and lemma 2.6, we have

$b\left(R\right)\le b\left(P\right)\le \lfloor \frac{V\left(R\right)}{2i}\rfloor +i\le \lfloor \frac{q\left(q+2-i\right)-3}{2i}\rfloor +i$

Let $f\left(i\right)=\lfloor \frac{q\left(q+2-i\right)-3}{2i}\rfloor +i$ , because of the properties of the function, the maximum is attained at the $q$ or $\lfloor \frac{q+4}{2}\rfloor$ .

Suppose $i=q$ , we have

$b\left(R\right)\le \lfloor \frac{V\left(R\right)}{2i}\rfloor +i=\lfloor \frac{q\left(q+2-i\right)-3}{2i}\rfloor +i=\lfloor \frac{2q-3}{2q}\rfloor +q\le q$

Suppose $i=\lfloor \frac{q+4}{2}\rfloor$ , we have

$\begin{array}{c}b\left(R\right)\le \lfloor \frac{V\left(R\right)}{2i}\rfloor +i=\lfloor \frac{q\left(q+2-i\right)-3}{2i}\rfloor +i\\ =\lfloor \frac{q\left(q+2-\lfloor \frac{q+4}{2}\rfloor -3\right)}{2\lfloor \frac{q+4}{2}\rfloor }\rfloor +\lfloor \frac{q+4}{2}\rfloor \end{array}$

when $q$ is even, then $\lfloor \frac{q+4}{2}\rfloor =\frac{q+4}{2}$ , we have $b\left(R\right)\le \lfloor \frac{q\left(q+2-\lfloor \frac{q+4}{2}\rfloor -3\right)}{2\lfloor \frac{q+4}{2}\rfloor }\rfloor +\lfloor \frac{q+4}{2}\rfloor =\lfloor \frac{q}{2}-\frac{2q+3}{q+4}\rfloor +\frac{q+4}{2}$ , since $\frac{2q+3}{q+4}\in \left(1,2\right)$ , then$\lfloor \frac{q}{2}-\frac{2q+3}{q+4}\rfloor =\frac{q}{2}-2$ , thus we have $b\left(R\right)\le \frac{q}{2}-2+\frac{q+4}{2}=q$ .

When $q$ is odd, then $\lfloor \frac{q+4}{2}\rfloor =\frac{q+4}{2}$ , we have $b\left(R\right)\le \lfloor \frac{q\left(q+2-\lfloor \frac{q+4}{2}\rfloor -3\right)}{2\lfloor \frac{q+4}{2}\rfloor }\rfloor +\lfloor \frac{q+4}{2}\rfloor =\lfloor \frac{q}{2}-1\rfloor +\frac{q+3}{2}$ , since $\lfloor \frac{q}{2}-1\rfloor =\frac{q-1}{2}-1$ , thus we have $b\left(R\right)\le \frac{q-1}{2}-1+\frac{q+3}{2}=q$ .

We know $G=N_q\left[x_1\right]\cup R$ , suppose $\left(z_1,z_2,\cdots ,z_q\right)$ is a burning sequence of $R$ . Next let $x_1=v_0$ and $x_{i+1}=z_i$ for $1\le i\le q$ , it is clear that $V\left(G\right)\subseteq N_q\left[x_1\right]\cup N_{q-1}\left[x_2\right]\cup N_{q-2}\left[x_3\right]\cup \cdots \cup N_0\left[x_{q+1}\right]$ , by lemma 2.1 we have $b\left(G\right)\le q+1$ .

Case 3 If $l\ge 2q$ .

When $l\ge 2q$ , we proceed with contradiction, assume $G^c$ is the minimal counterexample of octopus graph with order $n$ . This means

$b\left(G^c\right)>\lceil \sqrt{\left|b\left(G^c\right)\right|}\rceil =q+1$ . Suppose the length of longest arm $C_{l_i,2}$ of $G^c$ is $l$ , we have $w_1\in C_{l_i,2}$ such that $d\left(v_0,w_1\right)=l$ . Since $l\ge 2q$ , we have $w_0\in C_{l_i,2}$ satisfied $d\left(w_0,w_1\right)=q-1$ . We set $x_1$ at $w_0$ , Clearly, $N_q\left[w_0\right]$ can burn $2q+1$ vertices, We denoted $G_1=G\backslash N_q\left[w_0\right]$ where $v_0\in G_1$ , then $\left|G_1|=|G\backslash N_q\left[w_0\right]\right|\le q^2+2q+1-\left(2q+1\right)\le q^2$ . Consider $G^c$ is a counterexample of octopus with minimal number of vertices, we have $b\left(G_1\right)\le \lceil \sqrt{\left|G_1\right|}\rceil \le q$ , then $\left(z_1,z_2,\cdots ,z_q\right)$ is a burning sequence of $G_1$ . Next let $x_1=w_0$ , $x_{i+1}=z_i$ for $1\le i\le q$ , it is clear that $V\left(G^c\right)\subseteq N_q\left[x_1\right]\cup N_{q-1}\left[x_2\right]\cup N_{q-2}\left[x_3\right]\cup \cdots \cup N_0\left[x_{q+1}\right]$ . By lemma 2.1 we have $b\left(G^c\right)\le q+1$ . This contradicts to the fact $b\left(G^c\right)>q+1$ . Thus, we have $b\left(G\right)\le \lfloor \sqrt{n}\rfloor$ . □

Theorem 3.2 If $G=G_{v_0\left(g_1,g_2,a_1\right)}$ is a single tail bicyclic graph with order $n$ , then $\lceil \sqrt{n+\frac{21}{4}}-\frac{3}{2}\rceil \le b\left(G\right)\le \lceil \sqrt{n}\rceil$ .

Proof. We take a edge $e_i$ from $C_{g_i}$ (i = 1, 2), then we can derive

${G^{\prime }}_{v_0\left(g_1,g_2,a_1\right)}=G_{v_0\left(g_1,g_2,a_1\right)}-{\displaystyle \sum }_{i=1}^2{e}_i$ is a spider graph. By lemma 2.3 and lemma 2.5, we have $b(G_{v_0\left(g_1,g_2,a_1\right)}\le b\left({G^{\prime }}_{v_0\left(g_1,g_2,a_1\right)}\right)\le \lceil \sqrt{n}\rceil$ .

Next, we prove the lower bound, suppose $b\left(G\right)=k$ and $\left(x_1,x_2,\cdots ,x_k\right)$ is an optimal burning sequence of $G$ , we set $x_1$ on $v_0$ to contains more vertices, then, $N_{k-1}\left[x_1\right]\le 5\left(k-1\right)+1$ , combine with the fact that $\left|N_{k-i}\left[x_i\right]\right|\le 2\left(k-i\right)+1$ for $2\le i\le k$ , we get

$\begin{array}{c}\left|N_{k-1}\left[x_1\right]\right|+{\displaystyle \sum }_{i=2}^k\left(2\left(k-i\right)+1\right)\le \left(5\left(k-1\right)+1\right)+\left(2\left(k-2\right)+1\right)+\cdots +1\\ =\left(5k-4\right)+\left(2k-3\right)+\cdots +1\\ =k^2+3k-3.\end{array}$

by $k^2+3k-3\ge n$ , we have $k\ge \lceil \sqrt{n+\frac{21}{4}}-\frac{3}{2}\rceil$ . □

Theorem 3.3 If $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ is a double tail bicyclic graph with order $n$ , then $\lceil \sqrt{n+8}\rceil -2\le b\left(G\right)\le \lceil \sqrt{n}\rceil$ .

Proof. We take a edge $e_i$ from $C_{g_i}$ ( $i=1,2$ ), then we can derive ${G^{\prime }}_{v_0\left(g_1,g_2,a_1,a_2\right)}=G_{v_0\left(g_1,g_2,a_1,a_2\right)}-{\displaystyle \sum }_{i=1}^2{e}_i$ is a spider graph. by lemma 2.3 and lemma 2.5, we have $b\left(G_{v_0\left(g_1,g_2,a_1,a_2\right)}\right)\le b\left({G^{\prime }}_{v_0\left(g_1,g_2,a_1,a_2\right)}\right)\le \lceil \sqrt{n}\rceil$ .

Next, we prove the lower bound, suppose $b\left(G\right)=k$ and $\left(x_1,x_2,\cdots ,x_k\right)$ is an optimal burning sequence of $G$ . We set $x_1$ on $v_0$ to contains more vertices, then, $N_{k-1}\left[x_1\right]\le 6\left(k-1\right)+1$ , combine with the fact that $\left|N_{k-i}\left[x_i\right]\right|\le 2\left(k-i\right)+1$ for $2\le i\le k$ , we have

$\begin{array}{c}\left|N_{k-1}\left[x_1\right]\right|+{\displaystyle \sum }_{i=2}^k\left(2\left(k-i\right)+1\right)\le \left(6\left(k-1\right)+1\right)+\left(2\left(k-2\right)+1\right)+\cdots +1\\ =\left(6k-5\right)+\left(2k-3\right)+\cdots +1\\ =k^2+4k-4.\stackrel{}{}\end{array}$

by $k^2+4k-4\ge n$ , we have $k\ge \lceil \sqrt{n+8}\rceil -2$ . □

We following discuss the burning number of $G_{v_0\left(g_1,g_2,a_1\right)}$ and $G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ .

Consider $G=G_{v_0\left(g_1,g_2,a_1\right)}$ , by Theorem 3.2, we have

Corollary 3.4 If $G=G_{v_0\left(g_1,g_2,a_1\right)}$ is a single tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ , then $q-1\le b\left(G\right)\le q+1$ .

Next we discuss the graph $G_{v_0\left(g_1,g_2,a_1\right)}$ with burning number $q+1$ .

Theorem 3.5 Let $G=G_{v_0\left(g_1,g_2,a_1\right)}$ be a single tail bicyclic graph with order $q^2+p$ . If $3q-2\le p\le 2q+1$ , then $b\left(G\right)=q+1$

Proof. As we know from the previous, if $b\left(G\right)=q$ , then it can contains at most $q^2+3q-2$ vertices of $G$ . Since $3q-2\le p\le 2q+1$ , then we have $b\left(G\right)\ge q+1$ , combine with corollary 3.4, we have $b\left(G\right)=q+1$ . □

Theorem 3.6 Let $G=G_{v_0\left(g_1,g_2,a_1\right)}$ be a single tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $g_1\ge q^2$ or $a_1\ge q^2$ , then $b\left(G\right)=q+1$ .

Proof. We discuss two cases to complete the proof.

Case 1 If $g_1\ge q^2$ .

In this case, let $H=C_{g_1+1}$ , $\left|H\right|\ge q^2+1$ , by lemma 2.2, then $b\left(H\right)\ge q+1$ . If $\lceil \frac{g}{2}\rceil \le q$ and $a_1\le q$ , then $b\left(G\right)=b\left(H\right)\ge q+1$ . If $\lceil \frac{g}{2}\rceil \ge q$ or $a_1\ge q$ , then $b\left(G\right)\ge b\left(H\right)\ge q+1$ . Thus we have $b\left(G\right)\ge q+1$ , combine with corollary 3.4, we have $b\left(G\right)=q+1$ .

Case 2 If $a_1\ge q^2$ .

In this case, let $H=P_{a_1+1}$ , $\left|P_{a_1+1}\right|\ge q^2+1$ , by lemma 2.2, $b\left(H\right)\ge q+1$ . $H$ is a subgraph of $G$ , when $\lceil \frac{g_1}{2}\rceil \le q$ , we have $b\left(G\right)=b\left(H\right)\ge q+1$ , when $\lceil \frac{g_1}{2}\rceil >q$ , we have $b\left(G\right)>b\left(H\right)\ge q+1$ . Thus we have $b\left(G\right)\ge q+1$ , combine with corollary 3.4, we have $b\left(G\right)=q+1$ . □

Theorem 3.7 Let $G=G_{v_0\left(g_1,g_2,a_1\right)}$ be a single tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $\lceil \frac{g_1}{2}\rceil +a_1\ge q^2$ or $\lceil \frac{g_1}{2}\rceil +\lceil \frac{g_2}{2}\rceil \ge q^2$ , then

$b\left(G\right)=q+1$ . □

Proof. According to the definition of diameter, $d\left(G\right)=\max \left\{\lceil \frac{g_1}{2}\rceil +a_1,\lceil \frac{g_1}{2}\rceil +\lceil \frac{g_2}{2}\rceil \right\}$ , it’s clearly that $d\left(G\right)\ge q^2$ , by lemma 2.4, we have $b\left(G\right)\ge \lceil \sqrt{d\left(G\right)+1}\rceil \ge \lceil \sqrt{q^2+1}\rceil =q+1$ , combine with corollary 3.4, we have $b\left(G\right)=q+1$ .

Theorem 3.8 Let $G=G_{v_0\left(g_1,g_2,a_1\right)}$ be a single tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $2q-2\le g_1\le q^2+1$ , $2q-2\le g_2\le q^2+1$ , $q-1\le a_1\le q^2+1$

1) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}\ne 0$ , $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}\in J^1\cup J^2\cup J^3\cup J^4\cup J^5$ , then $b\left(G\right)=q+1$ .

2) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}=0$ , $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}\in J\left(t\right)$ , then $b\left(G\right)=q+1$ .

where ${g^{\prime }}_1=g_1-\left(2q-2\right),{g^{\prime }}_2=g_2-\left(2q-2\right),{a^{\prime }}_1=a_1-\left(2q-2\right)$ .

Proof. 1) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}\ne 0$ , suppose $\left(x_1,x_2,\cdots ,x_q\right)$ is an optimal burning sequence of $G$ , we set $x_1$ at $v_0$ , then $\left|N_{q-1}\left[x_1\right]\right|=5q-4$ , $H=G-N_{q-1}\left[x_1\right]=P_{{g^{\prime }}_1}\cup P_{{g^{\prime }}_2}\cup P_{{a^{\prime }}_1}$ . Since $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}\in J^1\cup J^2\cup J^3\cup J^4\cup J^5$ , by lemma 2.8, we have $b\left(H\right)=\lceil \sqrt{{g^{\prime }}_1+{g^{\prime }}_2+{a^{\prime }}_1}\rceil +1\le \lceil \sqrt{n-\left(5q-4\right)}\rceil +1\le \lceil \sqrt{{\left(q-1\right)}^2}\rceil +1\le q$ , then $b\left(G\right)=q+1$ , a contradiction, thus we have $b\left(G\right)\ge q+1$ , combine with corollary 3.4, we have $b\left(G\right)=q+1$ .

2) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}=0$ , suppose $\left(x_1,x_2,\cdots ,x_q\right)$ is an optimal burning sequence of $G$ , we set $x_1$ at $v_0$ , then $\left|N_{q-1}\left[x_1\right]\right|=5q-4$ ,

$H=G-N_{q-1}\left[x_1\right]=P_{{g^{\prime }}_1}\cup P_{{g^{\prime }}_2}\cup P_{{a^{\prime }}_1}$ . Since $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1\right\}\in J\left(t\right)$ , by lemma 2.7, we have $b\left(H\right)\le \lceil \sqrt{n-\left(5q-4\right)}\rceil +1\le \lceil \sqrt{{\left(q-1\right)}^2}\rceil +1\le q$ , then $b\left(G\right)=q+1$ , a contradiction, thus we have $b\left(G\right)\ge q+1$ . combine with corollary 3.4, we have $b\left(G\right)=q+1$ . □

Consider $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ , by Theorem 3.3, we have

Corollary 3.9 If $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ is a double tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ , then $q-1\le b\left(G\right)\le q+1$ .

Lemma 3.10 If G is disconnected with connected components $G_1,G_2,\cdots ,G_i$ , each $G_i$ contains no isolated vertices, then $b\left(G\right)\le b\left(G_1\right)+b\left(G_2\right)+\cdots +b\left(G_i\right)-i+1$ .

Proof. For each $G_j\left(1\le j\le i\right)$ , we suppose $X_j=\left(x_1^{\left(j\right)},x_2^{\left(j\right)},\cdots ,x_{b\left(G_j\right)}^{\left(j\right)}\right)$ is an optimal burning sequence, Clearly $G$ also has a burning sequence. We claim $X=\left(x_1^{\left(1\right)},\cdots ,x_{b\left(G_1\right)-1}^{\left(1\right)},x_1^{\left(2\right)},\cdots ,x_{b\left(G_2\right)-1}^{\left(2\right)},\cdots ,x_1^{\left(i\right)},\cdots ,x_{b\left(G_i\right)-1}^{\left(i\right)},x_{b\left(G_i\right)}^{\left(i\right)}\right)$ is a burning sequence of $G$ .

For each $j\in \left\{1,2,\cdots ,i-1\right\}$ , we burn $X\backslash \left\{x_{b\left(G_j\right)}^{\left(j\right)}\right\}$ in order. Before we burn $x_1^{\left(i\right)}$ , $C_{i-1}$ need at most 2 rounds to burn complete. Since $G_i$ contains no isolated vertices, then $b\left(G_i\right)\ge 2$ . Therefore, when $G_i$ is burned, $G_{i-1}$ has enough time to burn completely, thus all the $G_j$ can be burned completely. since $X$ is a valid burning sequence of $G$ , thus we have

$b\left(G\right)\le \left|X\right|=\left(b\left(G_1\right)-1\right)+\cdots +\left(b\left(G_i\right)-1\right)+b\left(G_i\right)=b\left(G_1\right)+b\left(G_2\right)+\cdots +b\left(G_i\right)-i+1$ .

□

Next we discuss $G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ with burning number $q+1$ .

Theorem 3.11 Let $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ be a double tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $q=2,p=5$ , then $b\left(G\right)=q+1$ .

Proof. If $q=2$ , then $n\in \left[5,9\left],p\in \right[1,5\right]$ . If $b\left(G\right)=q$ , it can contain at most $q^2+4q-4$ vertices. When $p\ge 4q-3$ , then $p=5$ , thus $b\left(G\right)\ge q+1$ . Combine with corollary 3.9, we have $b\left(G\right)=q+1$ . □

Theorem 3.12 Let $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ be a double tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $g_1\ge q^2$ or $a_1+a_2\ge q^2$ , then $b\left(G\right)=q+1$ .

Proof. We discuss two cases to complete the proof.

Case 1 If $g_1\ge q^2$ .

In this case, let $H=C_{g_1+1}$ , $\left|H\right|\ge q^2+1$ , by lemma 2.2, then $b\left(H\right)\ge q+1$ . Because of the symmetry of the circle, we set $x_1$ at $v_0$ . If $\max \left\{\frac{g_2}{2},a_1,a_2\right\}\le q$ , then $b\left(G\right)=b\left(H\right)\ge q+1$ , if $\max \left\{\frac{g_2}{2},a_1,a_2\right\}>q$ , then $b\left(G\right)>b\left(H\right)\ge q+1$ . Thus we can derive $b\left(G\right)\ge q+1$ , combine with corollary 3.9, we have $b\left(G\right)=q+1$

Case 2 If $a_1+a_2\ge q^2$ .

In this case, let $H=P_{a_1+a_2+1}$ , $\left|P_{a_1+a_2+1}\right|\ge q^2+1$ , by lemma 2.2, $b\left(H\right)\ge q+1$ . $H$ is a subgraph of $G$ , similar to case 1, we have $b\left(G\right)\ge b\left(H\right)\ge q+1$ , combine with corollary 3.9, we have $b\left(G\right)=q+1$ . □

Theorem 3.13 Let $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ be a double tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $\lceil \frac{g_i}{2}\rceil +a_i\ge q^2$ or $\lceil \frac{g_1}{2}\rceil +\lceil \frac{g_2}{2}\rceil \ge q^2$ , then $b\left(G\right)=q+1$ .

Proof. According to the definition of diameter,

$d\left(G\right)=\max \left\{\lceil \frac{g_i}{2}\rceil +a_i,\lceil \frac{g_1}{2}\rceil +\lceil \frac{g_2}{2}\rceil \right\}$ , it’s clearly that $d\left(G\right)\ge q^2+1$ , by lemma 2.4, we have $b\left(G\right)\ge \lceil \sqrt{d\left(G\right)+1}\rceil \ge \lceil \sqrt{q^2+1}\rceil =q+1$ , combine with corollary 3.9, we have $b\left(G\right)=q+1$ . □

Theorem 3.14 Let $G=G_{v_0\left(g_1,g_2,a_1,a_2\right)}$ be a double tail bicyclic graph with order $q^2+p$ for $1\le p\le 2q+1$ . If $2q-2\le g_1\le q^2+1$ , $2q-2\le g_2\le q^2+1$ , $q-1\le a_1\le q^2+1$ , $q-1\le a_2\le q^2+1$

1) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}\ne 0$ , $\lceil \sqrt{{g^{\prime }}_1}\rceil \ne 1$ , $\lceil \sqrt{{g^{\prime }}_2}\rceil \ne 1$ , $\lceil \sqrt{{a^{\prime }}_1}\rceil \ne 1$ , $\lceil \sqrt{{a^{\prime }}_2}\rceil \ne 1$ , $\lceil \sqrt{{g^{\prime }}_1}\rceil +\lceil \sqrt{{g^{\prime }}_2}\rceil +\lceil \sqrt{{a^{\prime }}_1}\rceil +\lceil \sqrt{{a^{\prime }}_2}\rceil \le q+3$ , then $b\left(G\right)=q+1$ .

2) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}=0$ , $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}\in J^1\cup J^2\cup J^3\cup J^4\cup J^5$ or $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}\in J\left(t\right)$ , then $b\left(G\right)=q+1$ .

where ${g^{\prime }}_1=g_1-\left(2q-2\right),{g^{\prime }}_2=g_2-\left(2q-2\right),{a^{\prime }}_1=a_1-\left(2q-2\right),{a^{\prime }}_2=a_2-\left(2q-2\right)$

Proof. 1) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}\ne 0$ , suppose $\left(x_1,x_2,\cdots ,x_q\right)$ is an optimal burning sequence of $G$ , we set $x_1$ at $v_o$ , then $\left|N_{q-1}\left[x_1\right]\right|=6q-5$ , $H=G-N_{q-1}\left[x_1\right]=P_{{g^{\prime }}_1}\cup P_{{g^{\prime }}_2}\cup P_{{a^{\prime }}_1}\cup P_{{a^{\prime }}_2}$ , Since $\lceil \sqrt{{g^{\prime }}_1}\rceil \ne 1$ , $\lceil \sqrt{{g^{\prime }}_2}\rceil \ne 1$ , $\lceil \sqrt{{a^{\prime }}_1}\rceil \ne 1$ , $\lceil \sqrt{{a^{\prime }}_2}\rceil \ne 1$ , $\lceil \sqrt{{g^{\prime }}_1}\rceil +\lceil \sqrt{{g^{\prime }}_2}\rceil +\lceil \sqrt{{a^{\prime }}_1}\rceil +\lceil \sqrt{{a^{\prime }}_2}\rceil \le q+3$ , by lemma 3.10, we have $b\left(H\right)\le \lceil \sqrt{{g^{\prime }}_1}\rceil +\lceil \sqrt{{g^{\prime }}_2}\rceil +\lceil \sqrt{{a^{\prime }}_1}\rceil +\lceil \sqrt{{a^{\prime }}_2}\rceil -4+1\le q$ , then $b\left(G\right)=q+1$ , a contradiction, thus we have $b\left(G\right)\ge q+1$ . combine with corollary 3.9, we have $b\left(G\right)=q+1$ .

2) If $\min \left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}=0$ , suppose $\left(x_1,x_2,\cdots ,x_q\right)$ is an optimal burning sequence of $G$ , we set $x_1$ at $v_o$ , then $\left|N_{q-1}\left[x_1\right]\right|=6q-5$ , $H=G-N_{q-1}\left[x_1\right]$

When $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}\in J^1\cup J^2\cup J^3\cup J^4\cup J^5$ , by lemma 2.8, then

$b\left(H\right)\le \lceil \sqrt{n-\left(6q-5\right)}\rceil +1\le \lceil \sqrt{{\left(q-2\right)}^2+2}\rceil +1\le q$ , then $b\left(G\right)=q+1$ , a contradiction, thus we have $b\left(G\right)\ge q+1$ . combine with corollary 3.9, we have $b\left(G\right)=q+1$ .

When $\left\{{g^{\prime }}_1,{g^{\prime }}_2,{a^{\prime }}_1,{a^{\prime }}_2\right\}\in J\left(t\right)$ , by lemma 2.7, we have

$b\left(H\right)=\lceil \sqrt{n-\left(6q-5\right)}\rceil +1\le \lceil \sqrt{{\left(q-2\right)}^2+2}\rceil +1\le q$ , then $b\left(G\right)=q+1$ , a contradiction, thus we have $b\left(G\right)\ge q+1$ . combine with corollary 3.9, we have $b\left(G\right)=q+1$ . □

4. Conclusion

In this paper, we put forward on the unions of paths and circlies and confirm the burning conjecture for octopus graphs and $t$ tail bicyclic graph ($t=1,2$ ), we also discuss the single tail bicyclic graph and double tail bicyclic graph with the burning number $q+1$ . The burning conjecture has been a topic of concern which be useful for information dissemination. Our study is meaningful and next we focus on the burning number for these graph. Besides we will extend graph burning to hypergraph and achieve more results.

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable comments and suggestions to improve the quality of this article. This research was supported by Qinghai Minzu University Innovative Project (No. 07M2024006), NSFC No. 12371352 and Qinghai provincial basic research project No. 2022-ZJ-753.