Jiaqing Wu, Yinkui Li^*
Department of Mathematics, Qinghai Minzu University, Xining, China.
DOI: 10.4236/jamp.2025.131007   PDF    HTML   XML   134 Downloads   837 Views   Citations

Abstract

Graph burning is a model for describing the spread of influence in social networks and the generalized burning number $b_r\left(G\right)$ of graph $G$ is a parameter to measure the speed of information spread on network $G$ . In this paper, we determined the generalized burning number of gear graph, which is useful model of social network. We also provided properties of the generalized burning number of sun graphs, including characterizations and bounds.

Keywords

Burning Number, Generalized Burning Number, Gear Graph, Sun Graph

Share and Cite:

1. Introduction

Graph burning is a discrete-time process on graphs, which is a model for describing the spread of influence in social networks. In [1], Bonato et al. introduced the burning number of graph $G$ to measure the speed of contagion spread on $G$ . Research on graph burning see [2]. In [3], authors generalized the concept of burning number $b\left(G\right)$ of graph $G$ and proposed the generalized burning $b_r\left(G\right)$ with $b_1\left(G\right)=b\left(G\right)$ .

For a given graph $G$ with the maximum degree $\text{Δ}\left(G\right)$ and a positive integer $1\le r\le \text{Δ}\left(G\right)$ , we defined a $r$ -burning process on $G$ : When $t=0$ , all vertices are unburned. At time $t\ge 1$ , an unburned vertex is chosen to burn (call it a fire source) and a vertex $v$ will be burned at time $t$ if and only if $v$ has at least $r$ neighbor vertices have been burned before time $t$ . They defined the generalized burning number of $G$ is the minimum number of time steps of $r$ -burning process of $G$ . If graph $G$ can be burned in $k$ steps and the $i$ -th fire source is $x_i\left(1\le i\le k\right)$ , the sequence $\left(x_1,x_2,\cdots ,x_k\right)$ call a $r$ -burning sequence of $G$ . Clearly, the generalized burning number $b_r\left(G\right)$ is the length of the shortest $r$ -burning sequence of $G$ , such sequence call an optimal $r$ -burning sequence of $G$ .

The gear graph $G_n$ is obtained from the wheel graph $W_n$ by adding a vertex between every pair of adjacent vertices of the $n$ -cycle. A sun graph is a graph obtained from a $g$ -cycle by attaching pendant edges to some vertices. We by

$S=\left\{S_g^{a_1,\cdots ,a_g}:n=g+{\displaystyle \sum }_{i=1}^g{a}_i\right\}$ denote the sun graph with $g$ -cycle $C_g=\left\{v_1,v_2,\cdots ,v_g\right\}$ and $v_i$ has $a_i$ leaf vertices (see Figure 1).

(a) gear graph $G_n$

(b) sun graph $S_g^{a_1,\cdots ,a_g}$

Figure 1. Gear graph $G_n$ and sun graph $S_g^{a_1,\cdots ,a_g}$ .

In [4], Wei et al. determined the Wiener index of gear graph. In [5], Prajapati et al. discussed the product cordial labeling of gear graph. Ali et al. studied the radio number of generalized gear graph in [6]. Khan determined the L(1,1,1)-chromatic number for sun graph in [7]. In this paper, we determined the generalized burning number of gear graph and sun graph.

All graphs considered in this paper are finite and simple. We use book [8] for notation and terminology not defined here. We by $d_G\left(u,v\right)$ denote the distance between vertex $u$ and $v$ , by $N_k\left[v\right]$ denote the $k$ -th closed neighborhood of $v$ . Without causing confusion, $d_G\left(u,v\right)$ and $N_1\left[v\right]$ are simplified by $d\left(u,v\right)$ and $N\left[v\right]$ , respectively.

2. Preliminaries

Proposition 2.1. [3] Let $C_n$ be a cycle of order $n$ . Then $b_2\left(C_n\right)=\lceil \frac{n}{2}\rceil +1$ .

A subgraph $H$ of graph $G$ is called an isometric subgraph if for every pair of nodes $u$ and $v$ in $H$ , we have that $d_H\left(u,v\right)=d_G\left(u,v\right)$ .

Proposition 2.2. [1] For any isometric subgraph $H$ of a graph $G$ , we have that $b\left(H\right)\le b\left(G\right)$ .

Proposition 2.3. [9] A graph $G$ satisfies $b\left(G\right)=2$ if and only if $G$ has order at least 2 and has maximum degree $n-1$ or $n-2$ .

Proposition 2.4. [9] For a cycle $C_n$ , we have $b\left(C_n\right)=\lceil \sqrt{n}\rceil$ .

Proposition 2.5. [9] 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_0\left[x_k\right]=V\left(G\right)$ , then $b\left(G\right)\le k$ .

3. Main Results

In this section, we determined the generalized burning number of gear graph and sun graphs and gave bound of the generalized burning number. By the definition of the generalized burning number, we directly get the following Lemma.

Lemma 3.1. Let $G$ be a connected graph of order $n$ and $1\le r\le \Delta \left(G\right)$ . If there are $k$ vertices with degree more than $r$ , then $n-k\le b_r\left(G\right)\le n$ .

Now we determined the generalized burning number of the gear graph $G_n$ .

Theorem 3.2. Let $G_n$ be a gear graph of order $2n+1$ for $n\ge 3$ . Then

$b_r\left(G_n\right)=\{\begin{array}{ll}3,\hfill & \text{if}r=1;\hfill \\ \lfloor \frac{n}{2}\rfloor +3,\hfill & \text{if}r=2;\hfill \\ n+2,\hfill & \text{if}r=3;\hfill \\ 2n,\hfill & \text{if}4\le r\le n.\hfill \end{array}$

Proof. Suppose $V\left(G_n\right)=\left\{v,v_1,v_2,\cdots ,v_n,w_1,w_2,\cdots ,w_n\right\}$ , we distinguish cases as follow.

Case 1. $r=1$

By Proposition 2.3, we know that $b\left(G_n\right)\ge 3$ . On the other hand, let $x_1=v$ , $x_2=v_1$ and $x_3=w_{n-1}$ . Consider $N_2\left[x_1\right]\cup N_1\left[x_2\right]\cup N_0\left[x_3\right]=V\left(G_n\right)$ , by Proposition 2.5, thus $b\left(G_n\right)\le 3$ . Hence, we have $b\left(G_n\right)=3$ .

Case 2. $r=2$

If $n$ is odd, let $n=2k-1$ , $x_1=v$ , $x_{k+2}=w_{n-2}$ and $x_i=w_{2i-3}$ for $2\le i\le k+1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{k+2}\right)$ is a 2-burning sequence of $G_n$ and thus $b_2\left(G_n\right)\le k+2$ . Now, suppose $\left(x_1,x_2,\cdots ,x_b\right)$ is an optimal 2-burning sequence of $G_n$ and $b\le k+1$ . Consider $x_1$ and $x_b$ can only burn themselves. The total number vertices of $G_n$ can be burned at most $2+4\left(b-2\right)=4b-6\le 4\left(k+1\right)-6=4k-2$ , a contradiction. Therefore,

$b_2\left(G_n\right)\ge k+2$ and $b_2\left(G_n\right)=k+2=\lfloor \frac{n}{2}\rfloor +3$ .

If $n$ is even, let $n=2k$ , $x_1=v$ , $x_{k+2}=w_{n-2}$ , $x_{k+3}=w_n$ and $x_i=w_{2i-3}$ for $2\le i\le k+1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{k+3}\right)$ is a 2-burning sequence of $G_n$ and thus $b_2\left(G_n\right)\le k+3$ . Conversely, suppose $\left(x_1,x_2,\cdots ,x_b\right)$ is an optimal 2-burning sequence of $G_n$ and $b\le k+2$ . Obviously, $x_1$ and $x_b$ can only burn themselves. Consider $x_2$ and $x_{b-1}$ can affect at most two neighboring vertices. After $b$ steps, the vertices of $G_n$ can be burned at most $8+4\left(b-4\right)=4b-8\le 4\left(k+2\right)-8=4k$ , a contradiction. Thus $b_2\left(G_n\right)\ge k+3$

and $b_2\left(G_n\right)=k+3=\lfloor \frac{n}{2}\rfloor +3$ .

Case 3. $r=3$

Let $x_{n+1}=v$ , $x_{n+2}=v_1$ and $x_i=w_i$ for $1\le i\le n$ . Clearly, $\left(x_1,x_2,\cdots ,x_{n+2}\right)$ is a 3-burning sequence of $G_n$ and thus $b_3\left(G_n\right)\le n+2$ . Next, we show $b_3\left(G_n\right)\ge n+2$ . Since $d\left(w_i\right)=2$ and $r=3$ for $1\le i\le n$ , then $w_i$ and $v$ must be fire sources in any optimum 3-burning sequence of $G_n$ . Moreover, there are at least one vertex of $v_i$ as fire source for $1\le i\le n$ . Therefore, $b_3\left(G_n\right)\ge n+2$ and $b_3\left(G_n\right)=n+2$ .

Case 4. $4\le r\le n$

In this case, $4\le r\le n$ , then $d\left(v\right)\ge r$ , and by Lemma 3.1, we get that $b_r\left(G_n\right)\ge 2n$ . Conversely, let $x_i=v_i$ for $1\le i\le n$ and $x_j=v_{j-n}$ for $n+1\le j\le 2n$ . Obviously, $\left(x_1,x_2,\cdots ,x_{2n}\right)$ be $r$ -burning sequence of $G_n$ and thus $b_r\left(G_n\right)\le 2n$ . Hence, we get $b_r\left(G_n\right)=2n$ . This completes the proof. □

Next, we determined the generalized burning number of $S_g^{a_1}$ .

Theorem 3.3. Let $S_g^{a_1}$ be a sun graph of order $n$ . Then

(1) $b\left(S_g^{a_1}\right)=\lceil \sqrt{g}\rceil$ ;

(2) $b_2\left(S_g^{a_1}\right)=\{\begin{array}{ll}\lceil \frac{g}{2}\rceil +1,\hfill & \text{if}{a}_1=1;\hfill \\ \lfloor \frac{g}{2}\rfloor +2,\hfill & \text{if}{a}_1=2;\hfill \\ a_1+\lceil \frac{g}{2}\rceil -1,\hfill & \text{if}{a}_1\ge 3.\hfill \end{array}$

(3) For $3\le r\le a_1+2$

$b_r\left(S_g^{a_1}\right)=\{\begin{array}{ll}n,\hfill & \text{if}r=a_1+2\text{and}g=3;\hfill \\ n-1,\hfill & \text{otherwise}.\hfill \end{array}$

Proof. Let $C_g=v_1{v}_2\cdots v_g{v}_1$ and suppose the leaf vertices of $v_1$ are $u_i$ for $1\le i\le a_1$ , we distinguish cases by $r$ to complete the proof.

Case 1. $r=1$

Let $k=\lceil \sqrt{g}\rceil$ , $x_1=v_1$ and $x_{k-i}=v_{n-i^2-i-k+1}$ for $0\le i\le k-2$ . Clearly, $\left(x_1,x_2,\cdots ,x_k\right)$ is a burning sequence of $S_g^{a_1}$ and thus $b\left(S_g^{a_1}\right)\le k=\lceil \sqrt{g}\rceil$ . On the other hand, $C_g$ is an isometric subgraph of $S_g^{a_1}$ . By Proposition 2.2 and Proposition 2.4, we directly get $b\left(S_g^{a_1}\right)\ge b\left(C_g\right)=\lceil \sqrt{g}\rceil$ . Hence, $b\left(S_g^{a_1}\right)=\lceil \sqrt{g}\rceil$ .

Case 2. $r=2$

First, consider the case for $a_1=1$ , let $x_{k+1}=u_1$ and $x_i=v_{2i-1}$ for $1\le i\le k$ . Clearly, $\left(x_1,x_2,\cdots ,x_{k+1}\right)$ is a 2-burning sequence of $S_g^{a_1}$ and thus

$b_2\left(S_g^{a_1}\right)\le k+1=\lceil \frac{g}{2}\rceil +1$ . Now, we show $b_2\left(S_g^{a_1}\right)\ge \lceil \frac{g}{2}\rceil +1$ . Since $a_1=1$ , by burning $u_1$ , we know that $v_1$ is unburned. Thus, the vertices of $C_g$ at least $\lceil \frac{g}{2}\rceil$ must be fire source. Because $u_1$ is leaf vertex, we get $b_2\left(S_g^{a_1}\right)\ge \lceil \frac{g}{2}\rceil +1$ . Then $b_2\left(S_g^{a_1}\right)=\lceil \frac{g}{2}\rceil +1$ .

Then, consider the case $a_1=2$ , If $g$ is odd, suppose $g=2k-1$ , otherwise, $g=2k$ . When $g$ is odd, let $x_1=u_1$ , $x_{k+1}=u_2$ and $x_i=v_{2i-2}$ for $2\le i\le k$ . Clearly, $\left(x_1,x_2,\cdots ,x_{k+1}\right)$ is a 2-burning sequence of $S_g^{a_1}$ and thus

$b_2\left(S_g^{a_1}\right)\le k+1=\lfloor \frac{g}{2}\rfloor +2$ . Next, we will show that $b_2\left(S_g^{a_1}\right)\ge \lceil \frac{g}{2}\rceil +1$ . Since $a_1=2$ , then $v_1$ can automatically burn. Hence, the vertices of $C_g$ at least $\lceil \frac{g-1}{2}\rceil$ must be fire source. The leaf vertices must be fire source, we have that $b_2\left(S_g^{a_1}\right)\ge \lceil \frac{g-1}{2}\rceil +2=\lfloor \frac{g}{2}\rfloor +2$ . Therefore, $b_2\left(S_g^{a_1}\right)=\lfloor \frac{g}{2}\rfloor +2$ .

Now, when $g$ is even, let $x_1=u_1$ , $x_{k+2}=u_2$ and $x_i=v_{2i-2}$ for $2\le i\le k+1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{k+2}\right)$ is a 2-burning sequence of $S_g^{a_1}$ , thus $b_2\left(S_g^{a_1}\right)\le k+2$ . To the contrary, suppose $\left(x_1,x_2,\cdots ,x_b\right)$ is an optimal 2-burning sequence of $S_g^{a_1}$ and $b\le k+1$ . Note that $x_1$ and $x_b$ only can burn themselves. Namely, after $b$ steps, the vertices of $S_g^{a_1}$ are burned at most $2+2\left(b-2\right)=2b-2\le 2k$ , a contradiction, we can conclude that $b_2\left(S_g^{a_1}\right)\ge k+2$ . Therefore,

$b_2\left(S_g^{a_1}\right)=k+2=\lceil \frac{g}{2}\rceil +2$ .

As for the general cases $a_1\ge 3$ . Let $x_1=u_1$ , $x_2=u_2$ , $x_i=v_{2i-3}$ for $3\le i\le k+1$ and $x_j=u_{j-k+1}$ for $k+2\le j\le a_1+k-1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{a_1+k-1}\right)$ is a 2-burning sequence of $S_g^{a_1}$ and thus $b_2\left(S_g^{a_1}\right)\le a_1+k-1=a_1+\lceil \frac{g}{2}\rceil -1$ . Conversely, $u_i$

must be fire source for $1\le i\le a_1$ . Suppose $x_k$ is the last fire source. If $a_1\ge 3$ , let $x_k\in u_i$ and $u_i$ cause $v_1$ to burn automatically for $1\le i\le a_1$ . Thus, the vertices

of $C_g$ at least $\lceil \frac{g}{2}\rceil -1$ must be fire source, we get $b_2\left(S_g^{a_1}\right)\ge a_1+\lceil \frac{g}{2}\rceil -1$ . Then $b_2\left(S_g^{a_1}\right)=a_1+\lceil \frac{g}{2}\rceil -1$ .

Case 3. $3\le r\le a_1+2$

When $r=a_1+2$ and $g=3$ , by simple checking, we directly get $b_r\left(S_g^{a_1}\right)=n$ . When $3\le r<a_1+2$ , since $d\left(v_1\right)\ge 3$ , combine Lemma 3.1, we have

$b_r\left(S_g^{a_1}\right)\ge n-1$ . On the other hand, let $x_i=v_{i+1}$ for $1\le i\le g-1$ and $x_j=u_{j-g+1}$ for $g\le i\le n-1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{n-1}\right)$ is a $r$ -burning sequence of $S_g^{a_1}$ and thus $b_r\left(S_g^{a_1}\right)\le n-1$ . □

Theorem 3.4. Let $S=S_g^{a_1,\cdots ,a_g}$ be a sun graph with $a_i=1$ for $1\le i\le g$ . Then

$b_r\left(S\right)=\{\begin{array}{ll}\lceil \sqrt{g-1}\rceil +1,\hfill & \text{if}r=1;\hfill \\ g+1,\hfill & \text{if}r=2;\hfill \\ g+\lceil \frac{g}{2}\rceil ,\hfill & \text{if}r=3.\hfill \end{array}$

Proof. Let $C_g=v_1{v}_2\cdots v_g{v}_1$ and suppose $u_i$ are leaf neighbors of the $v_i$ for $1\le i\le g$ .

Case 1. $r=1$

Let $k=\lceil \sqrt{g-1}\rceil +1$ , we first show that $b\left(S\right)\le k$ . Let $x_1=v_1$ , $x_k=v_k$ and $x_{k-i-1}=v_{n-i^2-i-k+2}$ for $0\le i\le k-2$ . Clearly, $\left(x_1,x_2,\cdots ,x_k\right)$ is a burning sequence of $S$ and thus $b\left(S\right)\le k$ .

Now, we show that $b\left(S\right)\ge k$ . If $g\le k^2-2k+2$ , suppose $\left(x_1,x_2,\cdots ,x_k\right)$ be an optimal burning sequence of $S$ . Since $k$ is the minimum number satisfying this inequality, we get $\lceil \sqrt{g-1}\rceil +1\le b\left(S\right)$ for $g\le k^2-2k+2$ . If $g>k^2-2k+2$ . Assume $\left(x_1,x_2,\cdots ,x_{\alpha }\right)$ is a burning sequence of $S$ , where $\alpha <k$ . For $1\le j\le \alpha$ , the fire source $x_j$ it can spread to the vertices of $N_{\alpha -j}\left[x_j\right]$ . For $1\le j\le \alpha -1$ , $N_{\alpha -j}\left[x_j\right]$ can contain at most $2\left(\alpha -j\right)-1$ leaf vertices of $S$ and $\left|N_0\left[x_{\alpha }\right]\right|=1$ .

Therefore, leaf vertices are burned at most $1+{\displaystyle \sum }_{j=1}^{\alpha -1}2\left(\alpha -j\right)-1={\alpha }^2-2\alpha +2$ . Note

that $\left|S\backslash C_g\right|=g>k^2-2k+2>{\alpha }^2-2\alpha +2$ , thus $b\left(S\right)\ge k$ . Therefore, $b\left(S\right)=k=\lceil \sqrt{g-1}\rceil +1$ .

Case 2. $r=2$

Let $x_1=v_1$ and $x_i=u_{i-1}$ for $2\le i\le g+1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{g+1}\right)$ is a 2-burning sequence of $S$ and thus $b_2\left(S\right)\le g+1$ . Now, we only need to show $b_2\left(S\right)\ge g+1$ . Consider $d\left(u_i\right)=1$ and $r=2$ for $1\le i\le g$ , thus all $u_i$ must be fire source. If all $a_i=1$ for $1\le i\le g$ , then at least one vertex of $C_g$ must also be selected as fire source. Therefore, $b_2\left(S\right)\ge g+1$ .

Case 3. $r=3$

When $g$ is odd, let $x_i=v_{2i-1}$ for $1\le i\le \lceil \frac{g}{2}\rceil$ and $x_j=u_{j-\lceil \frac{g}{2}\rceil }$ for $\lceil \frac{g}{2}\rceil +1\le j\le g+\lceil \frac{g}{2}\rceil$ . When $g$ is even, let $x_{g+\lceil \frac{g}{2}\rceil }=u_1$ , $x_i=v_{2i-1}$ for $1\le i\le \lceil \frac{g}{2}\rceil$ and $x_j=u_{j-\lceil \frac{g}{2}\rceil +1}$ for $\lceil \frac{g}{2}\rceil +1\le j\le g+\lceil \frac{g}{2}\rceil -1$ . Clearly, $\left(x_1,x_2,\cdots ,x_{g+\lceil \frac{g}{2}\rceil }\right)$ is a 3-burning sequence of $S$ and thus $b_3\left(S\right)\le g+\lceil \frac{g}{2}\rceil$ .

Now, we show $b_3\left(S\right)\ge g+\lceil \frac{g}{2}\rceil$ . Since $r=3$ and $d\left(u_i\right)$ for $1\le i\le g$ , thus all $u_i$ must be fire source. To burn all vertices of $S$ , there are at least $\lceil \frac{g}{2}\rceil$ vertices of $C_g$ as fire source, we get $b_3\left(S\right)\ge g+\lceil \frac{g}{2}\rceil$ . Then $b_3\left(S\right)=g+\lceil \frac{g}{2}\rceil$ . □

At the end of this section, we bounded of the generalized burning number of $S_g^{a_1,\dots ,a_g}$ .

Theorem 3.5. Let $S=S_g^{a_1,\cdots ,a_g}$ be a sun graph with a cycle $C_g=v_1{v}_2\cdots v_g$ and order $n$ , where $a_i\ge 1$ for $1\le i\le g$ . Then

(1) $\lceil \sqrt{g-1}\rceil +1\le b\left(S\right)\le \lceil \sqrt{g}\rceil +1$ ;

(2) $n-g\le b_2\left(S\right)\le n-g+1$ ;

(3) $n-\left|D_r\right|\le b_r\left(S\right)\le n-\lfloor \frac{\left|D_r|+|D_{r+1}\right|}{2}\rfloor$ for $3\le r\le \Delta \left(S\right)$ , where $D_r=\left\{v_i|d\left(v_i\right)\ge r,1\le i\le g\right\}$ .

Proof. First, when $r=1$ . Consider $S_g^{1,\cdots ,1}$ is an isometric subgraph of $S$ , by Proposition 2.2 and Theorem 3.4, we derive that $\lceil \sqrt{g-1}\rceil +1\le b\left(S\right)$ . Now, we show $b\left(S\right)\le \lceil \sqrt{g}\rceil +1$ . We set $k=\lceil \sqrt{g}\rceil +1$ , let $x_k=u_{g-4}$ and $x_{k-i}=v_{g-i^2+i}$

for $1\le i\le k-2$ . Also, if $g\ge {\left(k-1\right)}^2-k+3$ , we take $x_1=v_{g-{\left(k-1\right)}^2+\left(k-1\right)}$ ; otherwise $x_1=v_1$ . Clearly, $\left(x_1,x_2,\cdots ,x_k\right)$ is a burning sequence of $S$ . Hence, $b\left(S\right)\le k=\lceil \sqrt{g}\rceil +1$ .

Now, for $r=2$ . If $d\left(v_i\right)\ge 2$ for $1\le i\le g$ , by Lemma 3.1, then $b_2\left(S\right)\ge n-g$ . Now, we show $b_2\left(S\right)\le n-g+1$ . Let $u_i$ be leaf vertices of $S$ for $1\le i\le n-g$ . Without loss of generality, set $a_1\le a_i$ , for $2\le i\le g$ . Let $x_1=v_1$ and $x_i=u_{i-1}$ for $1\le i\le n-g+1$ . Obviously, $\left(x_1,x_2,\cdots ,x_{n-g+1}\right)$ is a 2-burning sequence of $S$ . Therefore, we get $b_2\left(S\right)\le n-g+1$ .

The general cases for $3\le r\le \Delta \left(S\right)$ . If $v\in D_r$ , Lemma 3.1, we gain that

$b_r\left(S\right)\ge n-\left|D_r\right|$ . Further, we will show that $b_r\left(S_1\right)\le n-\lfloor \frac{\left|D_r|+|D_{r+1}\right|}{2}\rfloor$ . The leaf

vertices and $\left\{v_i|d\left(v_i\right)<r,1\le i\le g\right\}$ must be fire sources in any $r$ -burning process of $S$ . Let $S_1=S_g^{a_1,\cdots ,a_g}$ with $a_1\ge a_2\ge \cdots \ge a_g$ . Clearly, $b_r\left(S_1\right)\ge b_r\left(S\right)$ . Further, by simple checking, we find that in any $r$ -burning process of $S_1$ , there

are at least $\left|D_{r+1}\right|+\frac{\left|D_r|-|D_{r+1}\right|}{2}$ vertices would be burned by some fire sources. Thus we have $b_r\left(S_1\right)\le n-\left(\left|D_{r+1}\right|+\frac{\left|D_r\right|-\left|D_{r+1}\right|}{2}\right)\le n-\lfloor \frac{\left|D_r\right|+\left|D_{r+1}\right|}{2}\rfloor$ . Hence,

$b_r\left(S\right)\le n-\lfloor \frac{\left|D_r\right|+\left|D_{r+1}\right|}{2}\rfloor$ . This completes the proof. □

By Theorem 3.5, we immediately get Corollary 3.6.

Corollary 3.6. Let $S=S_g^{a_1,\cdots ,a_t}$ be a sun graph with a cycle $C_g=v_1{v}_2\cdots v_g$ and order $n$ , where $t<g$ . Then

(1) $\lceil \sqrt{g}\rceil \le b\left(S\right)\le \lceil \sqrt{g-1}\rceil +1$ ;

(2) $n-\left|D_r\right|\le b_r\left(S\right)\le n-\lfloor \frac{\left|D_r\right|+\left|D_{r+1}\right|}{2}\rfloor$ for $2\le r\le \Delta \left(S\right)$ , where $D_r=\left\{v_i|d\left(v_i\right)\ge r,1\le i\le g\right\}$ .

Proof. For the case $r=1$ , if all $a_i\ge 1$ and exist $a_i=1$ for $1\le i\le g$ , then $S$ is denoted by $S_1$ . First, we show that $b\left(S_1\right)\ge \lceil \sqrt{g-1}\rceil +1$ . Note that $S_g^{1,\cdots ,1}$ is an isometric subgraph of $S_1$ . Combine Proposition 2.2 and Theorem 3.4, we get $\lceil \sqrt{g-1}\rceil +1=b\left(S_g^{1,\cdots ,1}\right)\le b\left(S_1\right)$ . Now, we will show $b\left(S_1\right)\le \lceil \sqrt{g-1}\rceil +1$ and set $k=\lceil \sqrt{g-1}\rceil +1$ . Without loss of generality, let $a_{g-4}=1$ and $w$ be leaf vertex of $v_{g-4}$ . Choose $x_k=w$ , $x_{k-1}=v_g$ , $x_{k-2}=v_{g-2}$ and $x_{k-i}=v_{g-1-i^2+i}$ for

$1\le i\le k-2$ . Also, if $g\ge {\left(k-1\right)}^2-k+3$ , we take $x_1=v_{g-1-{\left(k-1\right)}^2+\left(k-1\right)}$ ; otherwise

let $x_1=v_1$ . Clearly, $\left(x_1,x_2,\cdots ,x_k\right)$ is a burning sequence of $S_1$ , then $b\left(S_1\right)\le k=\lceil \sqrt{g-1}\rceil +1$ . Further, we know that $S$ is an isometric subgraph of $S_1$ , by Proposition 2.2, then $b\left(S\right)\le b\left(S_1\right)=\lceil \sqrt{g-1}\rceil +1$ .

Next, we show $b\left(S\right)\ge \lceil \sqrt{g}\rceil$ . Obviously, $S_g^{a_1}$ is an isometric subgraph of $S$ , by Proposition 2.2 and Theorem 3.3, we have $b\left(S\right)\ge b\left(S_g^{a_1}\right)=\lceil \sqrt{g}\rceil$ .

The general cases for $2\le r\le \Delta \left(S\right)$ , by Theorem 3.5, we directly get $n-\left|D_r\right|\le b_r\left(S\right)\le n-\lfloor \frac{\left|D_r\right|+\left|D_{r+1}\right|}{2}\rfloor$ . This completes the proof. □

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable comments and suggest to improve the quality of the article.

Funding

Supported by AFSFQH (2022-ZJ-753) and NSFC (12371352).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bonato, A., Janssen, J. and Roshanbin, E. (2014) Burning a Graph as a Model of Social Contagion. In: Bonato, A., Graham, F. and Prałat, P., Eds., Algorithms and Models for the Web Graph, Springer International Publishing, 13-22.[CrossRef]
[2]	Bonato, A. (2021) A Survey of Graph Burning. Contributions to Discrete Mathematics, 16, 185-197.[CrossRef]
[3]	Li, Y., Qin, X. and Li, W. (2021) The Generalized Burning Number of Graphs. Applied Mathematics and Computation, 411, Article ID: 126306.[CrossRef]
[4]	Gao, W. and Shi, L. (2014) Wiener Index of Gear Fan Graph and Gear Wheel Graph. Asian Journal of Chemistry, 26, 3397-3400.[CrossRef]
[5]	Prajapati, U.M. and Raval, K.K. (2016) Product Cordial Graph in the Context of Some Graph Operations on Gear Graph. Open Journal of Discrete Mathematics, 6, 259-267.[CrossRef]
[6]	Ali, M., Rahim, T.M., Ali, G., et al. (2012) An Upper Bound for the Radio Number of Generalized Gear Graph. Ars Combinatoria, 107, 161-168.
[7]	Khan, N. (2020) L(1, 1, 1)-Labeling of Path, Bouquet of Cycles and Sun Graph. Journal of Mathematical and Computational Science, 5, 1360-1374.
[8]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan.
[9]	Bonato, A., Janssen, J. and Roshanbin, E. (2015) How to Burn a Graph. Internet Mathematics, 12, 85-100.[CrossRef]