Qiuye Zhu, Jiaqing Wu, Yinkui Li^*
Department of Mathematics, Qinghai Minzu University, Xining, China.
DOI: 10.4236/am.2025.1612045   PDF    HTML   XML   53 Downloads   324 Views   Citations

Abstract

Graph burning is a model to describe the spread of social influence. In 2023, Song et al. proposed the Independent Cascade Graph Burning model, where a vertex $v$ can be burned by its burning neighbors $u$ and the influence that $u$ gives to $v$ is larger than a given threshold $\beta$ . The minimum number of time steps that can be chosen as rounds to burn the whole graph $G$ with the Independent Cascade Graph Burning model called the IC burning number $b_{\beta }\left(G\right)$ . In this paper, we determined the IC burning number for some graphs and operation graphs.

Keywords

IC Burning Number, Binary Tree, Spider, Sunflower Graph

Share and Cite:

1. Introduction

Graph burning is a discrete-time process on graphs [1], Bonato et al. introduced the concept of the burning number to measures the speed of contagion spread on a graph and denoted the burning number of graph $G$ by $b\left(G\right)$ in [2], some special classes of graphs has been studied, such as spider graphs [3], path forest [4], generalized Petersen graphs [5], theta graphs [6], caterpillars [7] and fence graphs [8]. For a survey on graph burning see [9]. Later, Li et al. [10] generalized the burning number and introduced the generalized burning number $b_r\left(G\right)$ of $G$ for $r\ge 1$ . Follow these, Song et al. [11] propose the Independent Cascade graph burning model of $G$ , where a burned vertex $v$ can burn its neighbor $w$ only if the influence that $v$ exerts on $w$ is larger than a given threshold $\beta$ . Note that when $\beta =0$ , it is a traditional burning problem. The task is still to find the minimum sequence of vertices that can burn the whole graph. The minimum number of time steps is IC burning number $b_{\beta }\left(G\right)$ of graph $G$ . In the burn process of IC model of graph $G$ , we call a vertex is fire source, it is selected to burn. For a given threshold $\beta$ , the $x_i$ is the $i$ -th fire source in the $\beta$ -burning process of $G$ . If $G$ are burned after $k$ time steps, we call the fire source sequence $\left(x_1,x_2,\cdots ,x_k\right)$ a $\beta$ -burning sequence of $G$ . Clearly, the IC burning number $b_{\beta }\left(G\right)$ is the minimum length among all $\beta$ -burning sequences of graph $G$ .

In reality, the influence $u$ receives from its neighbor $w$ is an arbitrary value in $\left[0,1\right]$ , we easily know whether a vertex can be burned by its neighbor depends heavily on its degree. For $v,u\in V\left(G\right)$ , the distance between them is denoted by $d\left(u,v\right)$ . The open neighborhood $N\left(v\right)$ is the set of vertices at distance one from a vertex $v$ . Clearly, the closed neighborhood $N\left[v\right]=N\left(v\right)\cup \left\{v\right\}$ . Given a positive integer $k$ and fraction $\beta \in \left[0,1\right]$ , the $k$ -th closed $\beta$ -neighborhood of $u$ is a set $\left\{v\in V\left(G\right):d\left(u,v\right)\le k,f\left(u\right)\ge \beta \right\}$ and is denoted by $N_{\beta }^k\left[v\right]$ , where $f\left(u\right)=\frac{1}{d\left(u\right)}$ .

For $h\ge 1$ , $k\ge 2$ , a perfect $k$ -ary tree with height $h$ , denoted $T_k^h$ , is a tree with $k^h$ leaves and a root vertex with degree $k$ whose distance to all the leaves is $h$ and all other internal vertices have degree $k+1$ . The height of a vertex is the number of edges present in the path connecting that vertex to a leaf vertex. We call the internal vertices that are the parents of leaves as parent-leaves.

A spider is a tree contain one vertex called the spider head with degree at least 3. In a spider graph, every leaf is connected to the head by a path which called an arm. we denote such a spider graph by $SP\left(s,r\right)$ if all the arms of the spider graph with maximum degree $s$ are of the same length $r$ .

A $\left(n,1\right)$ -lollipop graph $L_{n,1}$ is a graph with $V\left(L_{n,1}\right)=\left\{v,u_1,u_2,\cdots ,u_n\right\}$ and $E\left(L_{n,1}\right)=\left\{u_i{u}_j|i,j=1,2,\cdots ,n,i\ne j\right\}\cup \left\{v{u}_1\right\}$ , see Figure 1(a). A corona graph of $K_n$ and $K_1$ , denoted by $K_n\circ K_1$ , is graph with $V\left(K_n\circ K_1\right)=\left\{v_1,v_2,\cdots ,v_n,u_1,u_2,\cdots ,u_n\right\}$ and $E\left(K_n\circ K_1\right)=\left\{u_i{u}_j|i,j=1,2,\cdots ,n,i\ne j\right\}\cup \left\{v_i{u}_i|i=1,2,\cdots ,n\right\}$ , see Figure 1(b).

(a) (b)

Figure 1. $\left(n,1\right)$ -lollipop graph $L_{n,1}$ and corona graph $K_n\circ K_1$ .

All graphs considered in this paper are finite and simple. We use book [12] for notation and terminology not defined here. In this paper, we study the $\beta$ -burning problem on several graph including complete $k$ -ary tree, spider graphs, $\left(n,1\right)$ -lollipop graph, corona graph of $K_n$ and $K_1$ and other graphs such as sunflower graph, friendship graph and Dutch windmill graph.

2. Primarilies

Proposition 2.1. [11] $G$ is a connected graph with $n$ vertices and $f\left(v_i\right)<\beta$ for $1\le i\le k$ , where $0<\beta \le 1$ . Then, $k\le b_{\beta }\left(G\right)\le n$ .

Proposition 2.2. [11] $G$ is a graph with $n$ vertices and $\Delta \left(G\right)$ is the maximum degree. Then, $\left(x_1,x_2\right)$ is an optimum $\beta$ -burning sequence for $G$ if and only if one of the following conditions is met:

1) $\text{Δ}\left(G\right)=d\left(x_1\right)=n-1$ , and $f\left(w\right)\ge \beta$ for all $\forall w\in N\left(x_1\right)\backslash \left\{x_2\right\}$ .

2) $\text{Δ}\left(G\right)\ge d\left(x_1\right)=n-2$ , and $f\left(w\right)\ge \beta$ for all $\forall w\in N\left(x_1\right)$ .

In [13], Bonato et al. provide a number of properties of the burning number.

Proposition 2.3. [13] If $T$ is a tree and $H$ is a subtree of $T$ , then we have that $b\left(H\right)\le b\left(T\right)$ .

A subgraph $H$ of graph $G$ is called an isometric subgraph if we have $d_H\left(u,v\right)=d_G\left(u,v\right)$ .

Proposition 2.4. [13] Let $H$ be an isometric subgraph of a graph $G$ and for any node $x\in V\left(G\right)\backslash V\left(H\right)$ , and any positive integer $k$ , there exist a node $f_k\left(x\right)\in V\left(H\right)$ satisfies $N_k\left[x\right]\cap V\left(H\right)\subseteq N_k^H\left[f_k\left(x\right)\right]$ . Then we have that $b\left(H\right)\le b\left(G\right)$ .

Proposition 2.5. [13] For any graph $G$ with radius $r$ and diameter $d$ , we have that

$\lceil \sqrt{d+1}\rceil \le b\left(G\right)\le r+1.$

Proposition 2.6. [13] For a graph $G$ , we have that

$b\left(G\right)=\min \{b\left(T\right):T$ is a spanning subtree of $G\}.$

3. Main Results

In this section, we determined the IC burning number of some operation graphs. First, we consider the perfect binary tree, spider graphs, $\left(n,1\right)$ -lollipop graph, corona graph $K_n\circ K_1$ .

Theorem 3.1. Let $T_2^h$ be a perfect binary tree of height $h$ , where $h\ge 2$ . Then

$b_{\beta }\left(T_2^h\right)=\{\begin{array}{ll}h+1,\hfill & \text{If}0\le \beta \le \frac{1}{3};\hfill \\ \{\begin{array}{ll}3,\hfill & \text{If}h=2;\hfill \\ 2^h-2,\hfill & \text{If}h\ge 3.\hfill \end{array}\hfill & \text{If}\frac{1}{3}<\beta \le \frac{1}{2};\hfill \\ 2^h-1,\hfill & \text{If}\frac{1}{2}<\beta \le 1.\hfill \end{array}$

Proof. Let $s$ be the root of $T_2^h$ and the leaves of $T_2^h$ be $u_i$ for $1\le i\le 2^h$ . Suppose the parent-leaves of $T_2^h$ be $v_i$ for $1\le i\le 2^{h-1}$ .

Case 1: $0\le \beta \le \frac{1}{3}$

The $T_2^h$ has total $h+1$ levels, since $T_2^h$ has height $h$ . Suppose we let $x_1=s$ . At the $t$ -th step $\left(t=h+1\right)$ , the fire completes the burning of the $t$ -th level of $T_2^h$ . Therefore, $b_{\beta }\left(T_2^h\right)\le h+1$ . Now, suppose $S=\left(x_1,x_2,\cdots ,x_k\right)$ is a $\beta$ -burning sequence of $T_2^h$ , where $k<h+1$ . The fire source $x_i$ can spread to the vertices of $N_{k-i}\left[x_i\right]$ . For $1\le i\le k$ , $N_{k-i}\left[x_i\right]$ can contain at most $2^{k-i}$ leaf vertices of $T_2^h$ . Therefore, we burned at most ${\displaystyle \sum }_{i=1}^k{2}^{k-i}=2^k-1$ leaf vertices. Since the total number of leaves of $T_2^h$ is $2^h$ . Now, $2^h\ge 2^k>2^k-1$ , a contradiction, we have $b_{\beta }\left(T_2^h\right)\ge h+1$ . Thus $b_{\beta }\left(T_2^h\right)=h+1$ .

Case 2: $\frac{1}{3}<\beta \le \frac{1}{2}$

Let two children of $s$ be $s_1$ and $s_2$ . Suppose $S=\left\{s,u_1,u_2,\cdots ,u_{2^h}\right\}$ , $Y=\left\{s_1,s_2,v_1,v_2,\cdots ,v_{2^{h-1}}\right\}$ and $X=S\cup Y$ . The case for $h=2$ , by simple checking, we know that $b_{\beta }\left(T_2^h\right)=3$ . Next, the case $h\ge 3$ . Since $\frac{1}{3}<\beta \le \frac{1}{2}$ , thus $T_2^h\backslash S$ must be fire sources. Let $x_1=s_1$ , $x_2=s_2$ and $x_i=v_{i-2}$ for $3\le i\le 2^{h-1}+2$ . Further, we choose $T_2^h\backslash X$ as remain fire sources. Obviously, $\left(x_1,x_2,\cdots ,x_{2^h-2}\right)$ is a $\beta$ -burning sequence of $T_2^h$ and thus $b_{\beta }\left(T_2^h\right)\le 2^h-2$ . Now, we show $b_{\beta }\left(T_2^h\right)\ge 2^h-2$ . As $f\left(V\left(T_2^h\right)\backslash S\right)<\beta$ for $1\le i\le 2^h-2$ . By Proposition 2.1, we get $2^h-2\le b_{\beta }\left(T_2^h\right)$ . Then, $b_{\beta }\left(T_2^h\right)=2^h-2$ .

Case 3: $\frac{1}{2}<\beta \le 1$

Let $U=\left\{u_i|1\le i\le 2^h\right\}$ , $V=\left\{v_i|1\le i\le 2^{h-1}\right\}$ and $H=U\cup V$ . We choose $x_i=v_i$ for $3\le i\le 2^{h-1}$ and $V\left(T_2^h\right)\backslash H$ as remain fire sources. Thus, $b_{\beta }\left(T_2^h\right)\le 2^h-1$ . On the other hand, $f\left(V\left(T_2^h\right)\backslash U\right)<\beta$ for $1\le i\le 2^h-1$ , combine Proposition 2.1, we have $2^h-1\le b_{\beta }\left(T_2^h\right)$ . Therefore, $b_{\beta }\left(T_2^h\right)=2^h-1$ .

Corollary 3.2. Let $T_k^h$ be a perfect $k$ -ary tree of height $h$ and order $n$ , where $h\ge 3$ and $k\ge 3$ . Then

$b_{\beta }\left(T_k^h\right)=\{\begin{array}{ll}h+1,\hfill & \text{If}0\le \beta \le \frac{1}{k+1};\hfill \\ n-k^h-1,\hfill & \text{If}\frac{1}{k+1}<\beta \le \frac{1}{k};\hfill \\ n-k^h,\hfill & \text{If}\frac{1}{k}<\beta \le 1.\hfill \end{array}$

Proof. Let $s$ be the root of $T_k^h$ and the leaves of $T_k^h$ be $u_i$ for $1\le i\le k^h$ . Suppose the parent-leaves of $T_k^h$ be $v_i$ for $1\le i\le k^{h-1}$ .

For the case $0\le \beta \le \frac{1}{k+1}$ , consider $T_2^h$ is a subtree of $T_k^h$ . Combine Proposition 2.3 and Theorem 3.1, we directly get $b_{\beta }\left(T_k^h\right)\ge b_{\beta }\left(T_2^h\right)=h+1$ . On the other hand, the fact that $b_{\beta }\left(T_k^h\right)\le h+1$ can be determined by let $x_1=s$ . Then, $b_{\beta }\left(T_k^h\right)=h+1$ .

The case for $\frac{1}{k+1}<\beta \le \frac{1}{k}$ , let the children of $s$ be $s_i$ for $1\le i\le k$ . Suppose $S=\left\{u_i|1\le i\le k^h\right\}\cup \left\{s\right\}$ , $Y=\left\{s_i|1\le i\le k\right\}\cup \left\{v_j|1\le j\le k^{h-1}\right\}$ and $X=S\cup Y$ . Similarly with Theorem 3.1, we have that $b_{\beta }\left(T_k^h\right)\le n-k^h-1$ . Further, $f\left(V\left(T_k^h\right)\backslash S\right)<\beta$ , by Proposition 2.1, we directly get $n-k^h-1\le b_{\beta }\left(T_k^h\right)$ . Then, $b_{\beta }\left(T_k^h\right)=n-k^h-1$ .

Consider that $\frac{1}{k}<\beta \le 1$ , let $U=\left\{u_i|1\le i\le k^h\right\}$ , $V=\left\{v_i|1\le i\le k^{h-1}\right\}$ and $H=U\cup V$ . Similarly, we choose $V\left(T_k^h\right)\backslash U$ be fire sources. Clearly, $\left(x_1,x_2,\cdots ,x_{n-k^h}\right)$ is a $\beta$ -burning sequence of $T_k^h$ . So, $b_{\beta }\left(T_k^h\right)\le n-k^h$ . On the other hand, since $f\left(V\left(T_k^h\right)\backslash U\right)<\beta$ , combine Proposition 2.1, we have that $n-k^h\le b_{\beta }\left(T_k^h\right)$ . Therefore, $b_{\beta }\left(T_k^h\right)=n-k^h$ .

Theorem 3.3. Let $SP\left(s,r\right)$ be a spider graph of order $n$ for $s\ge r$ . Then

$b_{\beta }\left(SP\left(s,r\right)\right)=\{\begin{array}{ll}r+1,\hfill & \text{If}0\le \beta \le \frac{1}{2};\hfill \\ n-s,\hfill & \text{If}\frac{1}{2}<\beta \le 1.\hfill \end{array}$

Proof. Let leaf vertices of $SP\left(s,r\right)$ be $Y=\left\{v_i|1\le i\le s\right\}$ . Suppose the neighbour vertices of leaf vertices are $U=\left\{u_i|1\le i\le s\right\}$ and $X=Y\cup U$ .

The case for $0\le \beta \le \frac{1}{2}$ , we first discuss $SP\left(r,r\right)$ . The radius of $SP\left(r,r\right)$ is $r$ . So by Proposition 2.5, we have that $b_{\beta }\left(SP\left(r,r\right)\right)\le r+1$ . Now we show that $b_{\beta }\left(SP\left(r,r\right)\right)\ge r+1$ . Assume $b_{\beta }\left(SP\left(r,r\right)\right)\le r$ and $S=\left(x_1,x_2,\cdots ,x_t\right)$ is a $\beta$ -burning sequence of $SP\left(r,r\right)$ , where $t\le r$ . No fire source in $S$ shall be able to burn more than 1 leaf vertex in $SP\left(r,r\right)$ , since $d\left(v_i,v_j\right)=2r$ for $i,j=1,2,\cdots ,s$ and $i\ne j$ . Thus $S$ will be able to burn at most $t$ leaf vertices. This implies that at least 1 leaf vertex will be left unburned, a contradiction, thus we have that $b_{\beta }\left(SP\left(r,r\right)\right)\ge r+1$ . Therefore, $b_{\beta }\left(SP\left(r,r\right)\right)=r+1$ . As $SP\left(r,r\right)$ is a subtree of $SP\left(s,r\right)$ , by Proposition 2.4 and Proposition 2.5, we have $b_{\beta }\left(SP\left(s,r\right)\right)\le r+1$ .

For the case $\frac{1}{2}<\beta \le 1$ . Consider that $f\left(V\left(SP\left(s,r\right)\right)\backslash Y\right)<\beta$ , by Proposition 2.1, we have that $n-s\le b_{\beta }\left(SP\left(s,r\right)\right)$ . Now, we show that $b_{\beta }\left(SP\left(s,r\right)\right)\le n-s$ . Let $x_i=u_i$ for $1\le i\le s$ and $V\left(SP\left(s,r\right)\right)\backslash X$ be remain fire sources. Obviously, $\left(x_1,x_2,\cdots ,x_{n-s}\right)$ is a $\beta$ -burning sequence of $SP\left(s,r\right)$ and then $b_{\beta }\left(SP\left(s,r\right)\right)\le n-s$ . Further, we have that $b_{\beta }\left(SP\left(s,r\right)\right)=n-s$ for $\frac{1}{2}<\beta \le 1$ .

Theorem 3.4. Let $K_n\circ K_1$ be a corona graph of $K_n$ and $K_1$ with order $2n\left(n\ge 2\right)$ . Then

$b_{\beta }\left(K_n\circ K_1\right)=\{\begin{array}{ll}3,\hfill & \text{If}0\le \beta \le \frac{1}{n};\hfill \\ n,\hfill & \text{If}\frac{1}{n}<\beta \le 1.\hfill \end{array}$

Proof. Let $V\left(K_n\circ K_1\right)=\left\{v_1,v_2,\cdots ,v_n,u_1,u_2,\cdots ,u_n\right\}$ and $E\left(K_n\circ K_1\right)=\left\{u_i{u}_j|i,j=1,2,\cdots ,n,i\ne j\right\}\cup \left\{v_i{u}_i|i=1,2,\cdots ,n\right\}$ . The case for $0\le \beta \le \frac{1}{n}$ , combine Proposition 2.2, we directly get $b_{\beta }\left(K_n\circ K_1\right)\ge 3$ . Now, we show $b_{\beta }\left(K_n\circ K_1\right)\le 3$ . Let $x_1=u_1$ , $x_2=v_1$ and $x_3=v_n$ . Clearly, $\left(x_1,x_2,x_3\right)$ is a $\beta$ -burning sequence of $K_n\circ K_1$ and thus $b_{\beta }\left(K_n\circ K_1\right)\le 3$ . Therefore, $b_{\beta }\left(K_n\circ K_1\right)=3$ . Consider the case $\frac{1}{n}<\beta \le 1$ , let $x_i=u_i$ for $1\le i\le n$ . Clearly, $\left(x_1,x_2,\cdots ,x_n\right)$ is a $\beta$ -burning sequence of $K_n\circ K_1$ . Thus $b_{\beta }\left(K_n\circ K_1\right)\le n$ . Now, we show $b_{\beta }\left(K_n\circ K_1\right)\ge n$ . Obviously, $f\left(u_i\right)<\beta$ for $1\le i\le n$ . By Proposition 2.1, we get $n\le b_{\beta }\left(K_n\circ K_1\right)$ . Then, $b_{\beta }\left(K_n\circ K_1\right)=n$ .

Corollary 3.5. Let $L_{n,1}$ be a $\left(n,1\right)$ -lollipop of order $n+1$ . Then

$b_{\beta }\left(L_{n,1}\right)=\{\begin{array}{ll}2,\hfill & \text{If}0\le \beta \le \frac{1}{n-1};\hfill \\ n,\hfill & \text{If}\frac{1}{n-1}<\beta \le 1.\hfill \end{array}$

Proof. Let $V\left(L_{n,1}\right)=\left\{u,v_1,v_2,\cdots ,v_n\right\}$ and $E\left(L_{n,1}\right)=\left\{u_i{u}_j|i,j=1,2,\cdots ,n,i\ne j\right\}\cup \left\{v{u}_1\right\}$ . The case for $0\le \beta \le \frac{1}{n-1}$ , combining Proposition 2.2, we get $b_{\beta }\left(L_{n,1}\right)=2$ . For the case $\frac{1}{n-1}<\beta \le 1$ , similar as Theorem 3.4, the details omitted here, we have $b_{\beta }\left(L_{n,1}\right)=n$ .

Next, we determined the IC burning number of the sunflower graph, friendship graph and Dutch windmill graph.

A sunflower $S{f}_n$ is graph with $V\left(S{f}_n\right)=\left\{v,u_1,u_2,\cdots ,u_n,w_1,w_2,\cdots ,w_n\right\}$ and $\begin{array}{l}E\left(S{f}_n\right)=\left\{v{u}_i|i=1,2,\cdots ,n\right\}\cup \left\{u_i{w}_i|i=1,2,\cdots ,n\right\}\\ \cup \left\{w_i{u}_{i+1}|i=1,2,\cdots ,n\right\}\cup \left\{u_i{u}_{i+1}|i=1,2,\cdots ,n\right\}\end{array}$ , where edge $u_n{u}_{n+1}$ is $u_n{u}_1$ and $w_n{u}_{n+1}$ is $w_n{u}_1$ , see Figure 2(a).

(a) (b)

Figure 2. $S{f}_n$ with order $2n+1$ and $S{f}_n^I$ with order $3n+1$ .

An $I$ type sunflower $S{f}_n^I$ is a graph with $V\left(S{f}_n^I\right)=\left\{v,u_1,\cdots ,u_n,w_1,\cdots ,w_n\right\}$ and $\begin{array}{l}E\left(S{f}_n^I\right)=\left\{v{u}_i|i=1,2,\cdots ,n\right\}\cup \left\{v{w}_i|i=1,2,\cdots ,n\right\}\cup \left\{v{v}_i|i=1,2,\cdots ,n\right\}\\ \cup \left\{u_i{w}_i|i=1,2,\cdots ,n\right\}\cup \left\{u_i{u}_{i+1}|i=1,2,\cdots ,n\right\}\end{array}$ , where edge $u_n{u}_{n+1}$ is $u_n{u}_1$ , see Figure 2(b).

A friendship graph $F_n$ obtained $V\left(F_n\right)=\left\{v,v_1,v_2,\cdots ,v_n,u_1,u_2,\cdots ,u_n\right\}$ and $E\left(F_n\right)=\left\{v{v}_i|i=1,2,\cdots ,n\right\}\cup \left\{v{u}_i|i=1,2,\cdots ,n\right\}\cup \left\{u_i{v}_i|i=1,2,\cdots ,n\right\}$ , see Figure 3(a).

(a) (b)

Figure 3. $F_n$ with order $2n+1$ and $D_4^n$ with order $3n+1$ .

A Dutch windmill graph $D_4^n$ satisfied $V\left(D_4^n\right)=\left\{s\right\}\cup \left\{v_i,u_i,w_i|1\le i\le n\right\}$ and $\begin{array}{l}E\left(D_4^n\right)=\left\{s{u}_i|i=1,2,\cdots ,n\right\}\cup \left\{s{v}_i|i=1,2,\cdots ,n\right\}\\ \cup \left\{w_i{u}_i|i=1,2,\cdots ,n\right\}\cup \left\{w_i{v}_i|i=1,2,\cdots ,n\right\}\end{array}$ , see Figure 3(b).

Lemma 3.6. For a connected graph $G$ of order $n$ and $\delta \left(G\right)$ is the minimum degree of $G$ . Then, $b_{\beta }\left(G\right)=n$ if and only if $\beta >\frac{1}{\delta \left(G\right)}$ .

Proof. If $\beta >\frac{1}{\delta \left(G\right)}$ , then $f\left(V\left(G\right)\right)<\beta$ . By Proposition 2.1, we have that $n\le b_{\beta }\left(G\right)\le n$ . Therefore, $b_{\beta }\left(G\right)=n$ .

If $b_{\beta }\left(G\right)=n$ , suppose $\beta \le \frac{1}{\delta \left(G\right)}$ . Consider the minmum degree of $G$ is $\delta \left(G\right)$ and $\beta \le \frac{1}{\delta \left(G\right)}$ , then any vertex $u$ of $G$ receives influence from a neighbour is $f\left(u\right)=\frac{1}{d\left(u\right)}\ge \beta$ , thus we can selecte $n-1$ fire source to burn the whole graph $G$ , a contradiction, thus $\beta >\frac{1}{\delta \left(G\right)}$ .

Theorem 3.7. Let $S{f}_n$ be a sunflower graph of order $2n+1$ , where $n\ge 5$ . Then

$b_{\beta }\left(S{f}_n\right)=\{\begin{array}{ll}3,\hfill & \text{If}0\le \beta \le \frac{1}{5};\hfill \\ n+1,\hfill & \text{If}\frac{1}{5}<\beta \le \frac{1}{2};\hfill \\ 2n+1,\hfill & \text{If}\frac{1}{2}<\beta \le 1.\hfill \end{array}$

Proof. Let $V\left(S{f}_n\right)=\left\{v,u_1,u_2,\cdots ,u_n,w_1,w_2,\cdots ,w_n\right\}$ (see Figure 2(a)). The case for $0\le \beta \le \frac{1}{5}$ , by Proposition 2.2, we directly get $b_{\beta }\left(S{f}_n\right)\ge 3$ . On the other hand, let $x_1=v$ , $x_2=u_1$ and $x_3=w_1$ . Clearly, $\left(x_1,x_2,x_3\right)$ is a $\beta$ -burning sequence of $S{f}_n$ and thus $b_{\beta }\left(S{f}_n\right)\le 3$ . Then, $b_{\beta }\left(S{f}_n\right)=3$ . Consider the case $\frac{1}{5}<\beta \le \frac{1}{2}$ , let $X=\left\{u_i|1\le i\le n\right\}\cup \left\{v\right\}$ . Consider $f\left(X\right)<\beta$ , by Proposition 2.1, we have that $b_{\beta }\left(S{f}_n\right)\ge n+1$ . Now we show that $b_{\beta }\left(S{f}_n\right)\le n+1$ , let $x_{n+1}=v$ and $x_i=u_i$ for $1\le i\le n$ . Clearly, $\left(x_1,x_2,\cdots ,x_{n+1}\right)$ is a $\beta$ -burning sequence of $S{f}_n$ and thus $b_{\beta }\left(S{f}_n\right)\le n+1$ . Thus, $b_{\beta }\left(S{f}_n\right)=n+1$ . For the case $\frac{1}{2}<\beta \le 1$ , by Lemma 3.6, $\delta \left(G\right)=2$ and $\beta >\frac{1}{\delta \left(G\right)}$ , thus we directly get $b_{\beta }\left(S{f}_n\right)=2n+1$ .

Theorem 3.8. Let $S{f}_n^I$ be an $I$ type sunflower graph of order $3n+1$ . Then

$b_{\beta }\left(S{f}_n\right)=\{\begin{array}{ll}2,\hfill & \text{If}0\le \beta \le \frac{1}{4};\hfill \\ n+1,\hfill & \text{If}\frac{1}{4}<\beta \le \frac{1}{2};\hfill \\ 3n+1,\hfill & \text{If}\frac{1}{2}<\beta \le 1.\hfill \end{array}$

Proof. Let $V\left(S{f}_n^I\right)=\left\{v,u_1,u_2,\cdots ,u_n,w_1,w_2,\cdots ,w_n\right\}$ . The case for $0\le \beta \le \frac{1}{4}$ , consider $d\left(v\right)=3n$ , by Proposition 2.2, we directly get $b_{\beta }\left(S{f}_n^I\right)=2$ . The case for $\frac{1}{4}<\beta \le \frac{1}{2}$ , let $X=\left\{u_i|1\le i\le n\right\}\cup \left\{v\right\}$ . Consider $f\left(X\right)<\beta$ , by Proposition 2.1, we have that $b_{\beta }\left(S{f}_n^I\right)\ge n+1$ . Now we show that $b_{\beta }\left(S{f}_n\right)\le n+1$ . let $x_{n+1}=v$ and $x_i=u_i$ for $1\le i\le n$ . Clearly, $\left(x_1,x_2,\cdots ,x_{n+1}\right)$ is a $\beta$ -burning sequence of $S{f}_n^I$ and thus $b_{\beta }\left(S{f}_n\right)\le n+1$ . Thus, $b_{\beta }\left(S{f}_n^I\right)=n+1$ . For the case $\frac{1}{2}<\beta \le 1$ , similar as Theorem 3.7. We have $b_{\beta }\left(S{f}_n^I\right)=n+1$ .

Theorem 3.9. Let $F_n$ be a friendship graph of order $2n+1$ . Then

$b_{\beta }\left(F_n\right)=\{\begin{array}{ll}2,\hfill & \text{If}0\le \beta \le \frac{1}{2};\hfill \\ 2n+1,\hfill & \text{If}\frac{1}{2}<\beta \le 1.\hfill \end{array}$

Proof. Firstly, this case $0\le \beta \le \frac{1}{2}$ . Consider $d\left(v\right)=2n$ and all $f\left(V\left(F_n\right)\right)\ge \beta$ , by Proposition 2.2, we have that $b_{\beta }\left(F_n\right)=2$ . Now, consider $\frac{1}{2}<\beta \le 1$ . Clearly, if $\frac{1}{2}<\beta \le 1$ , we know that $f\left(V\left(F_n\right)\right)<\beta$ . Combine with Lemma 3.6, we directly get $b_{\beta }\left(F_n\right)=2n+1$ .

Theorem 3.10. Let $D_4^n$ be a Dutch windmill graph of order $3n+1$ . Then

$b_{\beta }\left(D_4^n\right)=\{\begin{array}{ll}\{\begin{array}{ll}2,\hfill & \text{If}n=1;\hfill \\ 3,\hfill & \text{If}n\ge 2.\hfill \end{array}\hfill & \text{If}0<\beta \le \frac{1}{2};\hfill \\ 3n+1,\hfill & \text{If}\frac{1}{2}<\beta \le 1.\hfill \end{array}$

Proof. For the case $0\le \beta \le \frac{1}{2}$ . If $n=1$ , by Theorem 3.8, we have that $b_{\beta }\left(D_4^n\right)=2$ . If $n\ge 2$ , let $x_1=v$ , $x_2=u_1$ and $x_3=w_1$ . Clearly, $\left(x_1,x_2,x_3\right)$ is a burning sequence of $D_4^n$ and thus $b_{\beta }\left(D_4^n\right)\le 3$ . Consider $b_{\beta }\left(D_4^n\right)\ge 3$ . When $0<\beta \le \frac{1}{2}$ , all $f\left(V\left(F_n\right)\right)\ge \beta$ . By Proposition 2.2, we gain $b_{\beta }\left(D_4^n\right)\ge 3$ and thus $b_{\beta }\left(D_4^n\right)=3$ . Now, consider the case $\frac{1}{2}<\beta \le 1$ . Clearly, if $\frac{1}{2}<\beta \le 1$ , we know that $f\left(V\left(D_4^n\right)\right)<\beta$ . by Lemma 3.6, we have $b_{\beta }\left(D_4^n\right)=3n+1$ .

Theorem 3.11. For a graph $G$ , let $H$ is a spanning subgraph of $G$ and $\forall v\in H$ , $d_H\left(v\right)=d_G\left(v\right)$ . Then $b_{\beta }\left(G\right)\le b_{\beta }\left(H\right)$ .

Proof. If $\beta =0$ , then it turns a traditional burning problem, combining Proposition 2.6, we have $b\left(G\right)\le b\left(H\right)$ . Now we consider $0<\beta \le 1$ , assume $b_{\beta }\left(H\right)=k$ , $\left(x_1,x_2,\cdots ,x_k\right)$ is a $\beta$ -burning sequence of $H$ . As $f\left(v\right)=\frac{1}{d\left(v\right)}$ and $d_H\left(v\right)=d_G\left(v\right)$ , therefore, for any vertex $v$ , the influence it receives from a neighbour is $f\left(v\right)=\frac{1}{d_H\left(v\right)}=\frac{1}{d_G\left(v\right)}$ , clearly, $\left(x_1,x_2,\cdots ,x_k\right)$ also can be $\beta$ -burning sequence of $G$ . We get $b_{\beta }\left(G\right)\le k$ , thus $b_{\beta }\left(G\right)\le b_{\beta }\left(H\right)$ .

Acknowledgements

This research was supported by NSFC No.12371352.

NOTES

*Corresponding author.

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., Lecture Notes in Computer Science, Springer International Publishing, 13-22.[CrossRef]
[2]	Bessy, S., Bonato, A., Janssen, J., Rautenbach, D. and Roshanbin, E. (2017) Burning a Graph Is Hard. Discrete Applied Mathematics, 232, 73-87.[CrossRef]
[3]	Bonato, A. and Lidbetter, T. (2019) Bounds on the Burning Numbers of Spiders and Path-Forests. Theoretical Computer Science, 794, 12-19.[CrossRef]
[4]	Liu, H., Hu, X. and Hu, X. (2021) Burning Numbers of Path Forests and Spiders. Bulletin of the Malaysian Mathematical Sciences Society, 44, 661-681.[CrossRef]
[5]	Sim, K.A., Tan, T.S. and Wong, K.B. (2017) On the Burning Number of Generalized Petersen Graphs. Bulletin of the Malaysian Mathematical Sciences Society, 41, 1657-1670.[CrossRef]
[6]	Liu, H., Zhang, R. and Hu, X. (2019) Burning Number of Theta Graphs. Applied Mathematics and Computation, 361, 246-257.[CrossRef]
[7]	Liu, H., Hu, X. and Hu, X. (2020) Burning Number of Caterpillars. Discrete Applied Mathematics, 284, 332-340.[CrossRef]
[8]	Bonato, A., English, S., Kay, B. and Moghbel, D. (2021) Improved Bounds for Burning Fence Graphs. Graphs and Combinatorics, 37, 2761-2773.[CrossRef]
[9]	Bonato, A. (2021) A Survey of Graph Burning. Contributions to Discrete Mathematics, 16, 185-197.[CrossRef]
[10]	Li, Y., Qin, X. and Li, W. (2021) The Generalized Burning Number of Graphs. Applied Mathematics and Computation, 411, Article 126306.[CrossRef]
[11]	Song, J., Qi, X. and Cao, Z. (2023) An Independent Cascade Model of Graph Burning. Symmetry, 15, Article 1527.[CrossRef]
[12]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan and Elsevier.
[13]	Bonato, A., Janssen, J. and Roshanbin, E. (2016) How to Burn a Graph. Internet Mathematics, 12, 85-100.[CrossRef]