Irreversible k-threshold conversion number of some graphs

Abstract

Purpose

This paper aims to study Irreversible conversion processes, which examine the spread of a one way change of state (from state 0 to state 1) through a specified society (the spread of disease through populations, the spread of opinion through social networks, etc.) where the conversion rule is determined at the beginning of the study. These processes can be modeled into graph theoretical models where the vertex set V(G) represents the set of individuals on which the conversion is spreading.

Design/methodology/approach

The irreversible k-threshold conversion process on a graph G=(V,E) is an iterative process which starts by choosing a set S_0?V, and for each step t (t = 1, 2,…,), S_t is obtained from S_(t−1) by adjoining all vertices that have at least k neighbors in S_(t−1). S_0 is called the seed set of the k-threshold conversion process and is called an irreversible k-threshold conversion set (IkCS) of G if S_t = V(G) for some t = 0. The minimum cardinality of all the IkCSs of G is referred to as the irreversible k-threshold conversion number of G and is denoted by C_k (G).

Findings

In this paper the authors determine C_k (G) for generalized Jahangir graph J_(s,m) for 1 < k = m and s, m are arbitraries. The authors also determine C_k (G) for strong grids P_2? P_n when k = 4, 5. Finally, the authors determine C_2 (G) for P_n? P_n when n is arbitrary.

Originality/value

This work is 100% original and has important use in real life problems like Anti-Bioterrorism.

Citation

Shaheen, R., Mahfud, S. and Kassem, A. (2024), "Irreversible k-threshold conversion number of some graphs", Arab Journal of Mathematical Sciences, Vol. 30 No. 1, pp. 43-56. https://doi.org/10.1108/AJMS-07-2021-0150

1. Introduction

As usual $n=\left|V\right|$ and $m=\left|E\right|$ denote the numbers of vertices and edges at a graph $G\left(V,E\right)$, respectively. Let $Y\subseteq V$ and let $F$ be a subset of $E$ such that $F$ consists of all edges of $G$ which have endpoints in $Y$, then $H=\left(Y,F\right)$ is called an induced subgraph of $G$ by $Y$ and is denoted by $G_Y.$ The open neighborhood of a vertex $v\in V$ is $N\left(v\right)=\left\{u\in V:uv\in E\right\}$ while the closed neighborhood of $v$ is $N\left[v\right]=N\left(v\right)\mathit{\cup }\left\{v\right\}$. The degree of a vertex $v$ is denoted by $\mathrm{d}\mathrm{e}\mathrm{g}\left(v\right)$ and $\mathrm{d}\mathrm{e}\mathrm{g}\left(v\right)=\left|N\left(v\right)\right|$. An independent vertex set of a graph $G\left(V,E\right)$ is a subset of $V$ such that no two vertices in the subset represent and edge of $G$. The independence number, denoted by $\alpha \left(G\right)$, is the cardinality of the largest independent vertex set of $G$. The term irreversible k-threshold conversion problem on graphs refers to the process of finding the least number of vertices we need to initially convert in step $t=0$ in order to get an irreversible k-threshold conversion process, which is an iterative process that starts by choosing a seed set $S_0\subseteq V$, and for each step $t\left(t=\mathrm{1,2},\dots ,\right),$ $S_t$ is obtained from $S_{t-1}$ by adjoining all vertices that have at least k neighbors in $S_{t-1}$.We call $S_0$ the seed set of the k-threshold conversion process and if $S_t=V\left(G\right)$ for some $t\ge 0$, then $S_0$ is an irreversible k-threshold conversion set (IkCS) of $G$. The k-threshold conversion number of $G$ (denoted by $C_k\left(G\right)$) is the minimum cardinality of all the IkCSs of $G.$ It is obvious that $1\le k\le \mathrm{\Delta }\left(G\right)$ and $C_1\left(G\right)=1$ for connected graphs. The first graph model of the Irreversible k-threshold conversion problem was presented by Dreyer and Roberts in Ref. [1] where they determined the value of $C_2\left(G\right)$ for paths and cycles. They also determined $C_2\left(G\right)\text{and}{C}_3\left(G\right)$ for grid graphs $P_3⊠P_n$. In Ref. [2] Kyn$č$l et al. found an upper bound for $C_k\left(G\right)$ of toroidal grids of size $m\times n$ if $m=4$ or $n=4$. In Ref. [3] Adams et al. presented an upper bound for $C_k\left(G\right)$ of the tensor product of two arbitrary graphs $G$ and $H$. In Ref. [4] Mynhardt and Wodlinger presented a lower bound for $C_k\left(G\right)$ of graphs of maximum degree $k+1.$ Frances et al. [5] studied the relationship between IkCSs and minimum decycling sets. An upper bound for $C_k\left(G\right)$ of regular graphs was presented by Mynhardt and Wodlinger in Ref. [6]. In Ref. [7] Shaheen et al. studied irreversible k-threshold conversion processes on circulant graphs. In Ref. [8] Shaheen et al. determined $C_2\left(G\right)\text{and}{C}_3\left(G\right)$ for the strong grid graphs $P_m⊠P_n$ when $m=\mathrm{2,3}$. For further information on the irreversible k-threshold conversion problem on graphs see Centeno et al. [9], Takaoka and Ueno [10], Kyn$č$l et al. [11]. A generalized Jahangir graph $J_{s,m}form\ge 2$ is a graph on $sm+1$vertices, i.e. a graph consisting of a cycle $C_{sm}$with one additional vertex which is adjacent to m vertices of $C_{sm}$ at distance $s$ from each other on $C_{sm}$, see Ref. [12] for more information on Jahangir graph. Let $v_{sm+1}$ be the label of the central vertex and $v_1,v_2,\dots ,v_{sm}$ be the labels of the vertices that incident clockwise on cycle $C_{sm}$ so that $\mathrm{d}\mathrm{e}\mathrm{g}\left(v_1\right)=3$. We will use this labeling for the rest of the article. The vertices that are adjacent to $v_{sm+1}$ have the labels $v_1,v_{1+s},v_{1+2s},\dots v_{1+\left(m-1\right)s}.$ Let $P_m$, $P_n$ be two paths, we define the strong product of $P_m$ and $P_n$ (also called strong grid graph) as the graph $P_m⊠P_n$ such that $V\left(P_m⊠P_n\right)=\left\{\left(i,j\right):1\le i\le m,1\le j\le n\right\}$ and two vertices $\left(i_1,j_1\right),\left(i_2,j_2\right)$ are adjacent if and only if $\mathit{max}\left\{\left|i_2-i_1\right|,\left|j_2-j_1\right|\right\}=1.$ See Ref. [13] for more information on strong grids$.$

Proposition 1.1.

[3] For $n\ge 2;C_2\left(P_n\right)=\frac{n+1}{2}.$

Proposition 1.2.

[3] $\mathrm{F}\mathrm{o}\mathrm{r}n\ge 3;C_2\left(C_n\right)=\frac{n}{2}.$

Proposition 1.3.

[13] For $n\ge 2;C_2\left(P_2⊠P_n\right)=2.$

Proposition 1.4.

[13] $\mathrm{F}\mathrm{o}\mathrm{r}n\ge 2;C_3\left(P_2⊠P_n\right)=n+1.$

Proposition 1.5.

[6] $\text{For}m,n\ge 2;\alpha \left(P_m⊠P_n\right)=\frac{m}{2}\frac{n}{2}.$

• Note 1: As an immediate consequence of the definition, $C_k\left(G\right)\ge k$ for any graph $G$.

• Note 2: As an immediate consequence of the definition, when studying an irreversible k-threshold conversion process on a graph $G\left(V,E\right)$ all vertices $\left\{v\in V;\mathrm{d}\mathrm{e}\mathrm{g}\left(v\right)<k\right\}$ must be included in the seed set $S_0$, otherwise the process will fail because none of these vertices can satisfy the conversion rule.

• Note 3: For Jahangir graph $J_{s,m},$ we denote the set of vertices of degree 3 which consists of $v_1,v_{1+s},\dots v_{1+\left(m-1\right)s}$ by $R.$ So, $R=\left\{v_{1+is}:i=\mathrm{0,1},\dots ,m-1\right\}.$

• Note 4: In every figure of this article, we assign the black color to the converted vertices and the white color to unconverted ones$.$

2. Main results

In this section we determine $C_k\left(G\right)$ for generalized Jahangir graph $J_{s,m}$ for $1<k\le m$ and $s,m$ are arbitraries. We also determine $C_k\left(G\right)$ for strong grids $P_2⊠P_n$ when $k=\mathrm{4,5}.$ Then we determine $C_2\left(G\right)$ for $P_n⊠P_n$ when $n$ is arbitrary.

2.1 $C_{\mathit{k}}\left(J_{s,m}\right)$

In this sub-section we find $C_k\left(G\right)$ of generalized Jahangir graph $J_{s,m}$ for $1<k\le m$ and $s,m$ are arbitraries.

Theorem 2.1.

$Fors,m\ge 2,C_2\left(J_{s,m}\right)=\frac{m\left(s-1\right)}{2}+1.$

Proof.

Let $J_{s,m}$ be a Jahangir graph on which an irreversible 2-threshold conversion process is being studied with a seed set $S_0$, let $U\mathit{\subseteq }V-S_0$ and $v_{sm+1}\notin U$, then $\mathit{U}$ is a 2-unconvertible set of $J_{s,m}$ if it satisfies the following condition:

$\text{For}\text{all}u\in U:\left|N\left(u\right)\cap U\right|\ge 2.$

Which means each vertex $u\in U$ is unconverted and is adjacent to at least $2$ vertices of $U$ at $t=0$. Since $\mathrm{d}\mathrm{e}\mathrm{g}\left(u\right)\le 3$ then $\left|N\left(u\right)\cap S_0\right|<2$ and the conversion cannot reach any vertex of $U$ during any step of the process. Therefore, we try to avoid having any version of $U$ on $J_{s,m}$when choosing $S_0$. We imply that the following sets $A_1=\left\{a,b,c\right\}$ with $(\mathrm{d}\mathrm{e}\mathrm{g}\left(a\right)=\mathrm{d}\mathrm{e}\mathrm{g}\left(c\right)=2$ and $\mathrm{d}\mathrm{e}\mathrm{g}\left(b\right)=3)$, $B_1=\left\{x,y\right\}$ (with $\mathrm{d}\mathrm{e}\mathrm{g}\left(x\right)=\mathrm{d}\mathrm{e}\mathrm{g}\left(y\right)=2$) are 2-unconvertible sets on $J_{s,m}$. Both $A_1$ and $B_1$ are represented in Figure 1.

By Proposition 1.1, we have $C_2\left(P_n\right)=\frac{n+1}{2}.$ It is obvious that the $\frac{n+1}{2}-$IkCS of a path $P_n$ must contain the end vertices $\left\{v_1,v_n\right\}$ otherwise the spread will never reach them. The vertices of $R$ divide $C_{sm}$ into $m$ paths (each of which consists of $s-1$ vertices and they are separated by the vertices of $R$). We denote these paths as follows:

$\begin{array}{l}{P}_{s-1}^{\left(1\right)}=v_2\dots v_s,\\ P_{s-1}^{\left(2\right)}=v_{2+s}\dots v_{2s},\\ ⋮\\ P_{s-1}^{\left(m\right)}=v_{2+\left(m-1\right)s}\dots v_{ms}.\end{array}$

We consider the following subcases:

Case 1. $s$ is even.

In this case, each path $P_{s-1}^{\left(i\right)}:1\le i\le m$ contains an odd number of vertices. We divide $V\left(P_{s-1}^{\left(i\right)}\right)$ into two sets:

$E{P}_i=\left\{v_{2+\left(i-1\right)s},v_{4+\left(i-1\right)s},\dots ,v_{is}\right\}\mathrm{w}\mathrm{h}\mathrm{i}\mathrm{c}\mathrm{h}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{s}\mathrm{o}\mathrm{f}\frac{s-1}{2}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}.$

$O{P}_i=\{\begin{array}{l}\varnothing ifs=2;\\ \left\{v_{3+\left(i-1\right)s},v_{5+\left(i-1\right)s},\dots ,v_{is-1}\right\}whichconsistsof\frac{s-1}{2}verticesifs\ge 4.\end{array}$

We define a family of sets $D=\{D_i:1\le i\le m,\text{where}{D}_i=\left\{\begin{array}{l}E{P}_{i}ifiisodd;\\ O{P}_{i}ifiiseven.\end{array}\right\}$

The process goes as follows:

• $t=0$: We convert the vertices of $S_0=D\cup \left\{v_{sm+1}\right\}.$

• $t=1$: The conversion spreads to:

  • The vertices of $\left\{O{P}_i:iisodd\right\}.$.

  • The vertices of $\left\{E{P}_i-\left\{v_{2+\left(i-1\right)s},v_{is}\right\}:iiseven\right\}.$.

  • The vertices of degree 3 (vertices of $R$).

• $t=2:$ The conversion spreads to $\left\{v_{2+\left(i-1\right)s},v_{is}:iiseven\right\}.$.

By the end of step $t=2$, the conversion is spread to $V\left(J_{s,m}\right)$ entirely and the process succeeds. It is obvious that $\left|S_0\right|=\{\begin{array}{l}\frac{m}{2}\left(\frac{s-1}{2}+\frac{s-1}{2}\right)+1ifmiseven;\\ \frac{m}{2}\frac{s-1}{2}+\frac{m}{2}\frac{s-1}{2}+1ifmisodd.\end{array}$

Which means:

(1)$C_2\left(J_{s,m}\right)\le \frac{m\left(s-1\right)}{2}+1$

Figure 2 shows that $C_2\left(J_{\mathrm{6,4}}\right)\le 11.$

We imply that the sets $A_1=\left\{a,b,c\right\}$, $B_1=\left\{x,y\right\}$ represented in Figure 1 are 2-unconvertible on $J_{s,m}$. We notice that $D$ is the only $\frac{m\left(s-1\right)}{2}$ - seed set that does not leave any versions of $A_1$ or $B_1$ on $C_{sm}$ and every $k$-seed set with $k<\frac{m\left(s-1\right)}{2}$ will leave some versions of $A_1$ or $B_1$ on $C_{sm}$. Let us assume that $D_0$ is a IkCS of cardinality $\frac{m\left(s-1\right)}{2}$, we consider the following subcases:

Case 1.a. $v_{sm+1}\notin D_0$, which means $D_0\mathit{\subseteq }V\left(C_{sm}\right)$, and since $\left|D_0\right|=\frac{m\left(s-1\right)}{2}$, then $D_0=D$ as we found earlier. However, since $C_2\left(C_{sm}\right)=\frac{sm}{2}$ by Proposition 1.2, it is impossible to convert all the vertices of $C_{sm}$ depending only on $D$. Therefore, we need to convert $v_{sm+1}$ at some point and benefit from it being adjacent to $m$ vertices of $C_{sm}$. To achieve that we need at step $t=0$ to choose one of three strategies:

• Convert 2 vertices of $R$ (e.g. $v_1,v_{1+s}$). However, that leaves $\frac{m\left(s-1\right)}{2}-2$ vertices in $D_0$ which means we end up with at least two versions of $B_1$ and the process fails as shown in Figure 3(a). Without loss of generality, any choice of the two vertices of $R$ leads to the same result.

• Convert 1 vertex of $R$ (e.g. $v_1$), and 2 vertices that are adjacent to a vertex of $R$ (for example $v_{2s},v_{2+2s}$), by converting the remaining $\frac{m\left(s-1\right)}{2}-3$ vertices in $D_0$ in a similar way to $D$, we end up with two versions of $B_1$ and the process fails as shown in Figure 3(b). Without loss of generality, any choice of the one vertex of $R$ and the two vertices that are adjacent to a vertex of $R$ leads to the same result.

• Convert 2 pairs of vertices each of which is adjacent to one vertex of $R (\mathrm{e}.\mathrm{g}.v_2,v_{sm},v_s,v_{2+s}),$ by converting the remaining $\frac{m\left(s-1\right)}{2}-4$ vertices in $D_0$ in a similar way to $D$, we end up with two versions of $B_1$ and the process also fails as shown in Figure 3(c). Without loss of generality, the same result is obtained for whatever 4 vertices that each of which is adjacent to a vertex of $R$ we choose to initially convert.

All strategies end up with two versions of $B_1$ on $C_{sm}$, and without loss of generality, we get the same results by choosing different vertices that satisfy the conditions mentioned in the three strategies above, therefore $C_2\left(J_{s,m}\right)>\frac{m\left(s-1\right)}{2}$ when $s$ is even and $v_{sm+1}\mathit{\notin }{D}_0$.

Case 1.b. $v_{sm+1}\in D_0$, by converting $\frac{m\left(s-1\right)}{2}$ vertices of $C_{sm}$ we end up with two versions of $B_1$ (as shown in Figure 3(d)), and the process fails. Therefore, $C_2\left(J_{s,m}\right)>\frac{m\left(s-1\right)}{2}$ in this case as well.

From Case 1.a and Case 1.b we conclude that:

(2)$Fors\text{is}\text{even},C_2\left(J_{s,m}\right)>\frac{m\left(s-1\right)}{2}.$

From (1) and (2) we conclude that for $s\text{is}\text{even};$ $C_2\left(J_{s,m}\right)=\frac{m\left(s-1\right)}{2}+1$.

Case 2. $s$ is odd.

In this case, each path $P_{s-1}^{\left(i\right)}:1\le i\le m$ contains an even number of vertices. We define a family of sets $D=\left\{D_i:1\le i\le m\right\}\text{where}{D}_i=\left\{v_{2+\left(i-1\right)s},v_{4+\left(i-1\right)s},\dots ,v_{is-1}\right\}$ which contains $\frac{m\left(s-1\right)}{2}$ vertices. The process goes as follows:

1. $t=0$: We convert the vertices of $S_0=D\cup \left\{v_{sm+1}\right\}$.

2. $t=1:$ The conversion spreads to the vertices of $\left\{D_i-\left\{v_{is-1}\right\}:1\le i\le m\right\}$.

3. $t=2:$ The conversion spreads to $\left\{v_{is-1}:1\le i\le m\right\}\text{.}$

By the end of step $t=2$, the conversion is spread to $V\left(J_{s,m}\right)$ entirely and the process succeeds.

It is obvious that $\left|S_0\right|=\frac{m\left(s-1\right)}{2}+1$ which means $C_2\left(J_{s,m}\right)\le \frac{m\left(s-1\right)}{2}+1.$ In a similar way to Case 1, $S_0$ is the only IkCS of cardinality $\frac{m\left(s-1\right)}{2}+1$ because $D$ is the only set of cardinality $\frac{m\left(s-1\right)}{2}$ that does not leave any versions of $A_1$ or $B_1$ on $C_{sm}$. By following the same discussion in Case 1 we conclude that $C_2\left(J_{s,m}\right)>\frac{m\left(s-1\right)}{2}$ if $s$ is odd, which means $C_2\left(J_{s,m}\right)=\frac{m\left(s-1\right)}{2}+1$ if $s$ is odd.

Figure 4 illustrates a 2-conversion process on $J_{\mathrm{7,4}}$ starting with $\left|S_0\right|=13.$

From Case 1 and Case 2 we conclude that $C_2\left(J_{s,m}\right)=\frac{m\left(s-1\right)}{2}+1$ for $s\ge 2$.

Theorem 2.2.

$Form\ge 2,$ $C_3\left(J_{s,m}\right)=m\left(s-1\right)+1.$

Proof.

By definition all vertices with degree lower than 3 need to be added to the seed set $S_0$. However, in order to convert a vertex of degree 3, we need it to be adjacent to three converted vertices which means the conversion will not spread unless $v_{sm+1}$ is initially converted. The process goes as follows:

• $t=0:$ We convert the vertices of $S_0=\left\{V\left(C_{sm}\right)-R\right\}\cup \left\{v_{sm+1}\right\}$, we implied that this set is unique.

• $t=1:$ The conversion spreads to the vertices of $R$.

The process succeeds and $J_{s,m}$ is entirely converted by the end of step 2 which means that $C_3\left(J_{s,m}\right)\le m\left(s-1\right)+1$, since $S_0$ is unique and none of its vertices can be removed, then $C_3\left(J_{s,m}\right)=m\left(s-1\right)+1$.

Theorem 2.3.

$For4\le k\le m,$ $C_k\left(J_{s,m}\right)=sm.$

Proof.

By definition all vertices with degree lower than 4 need to be included in $S_0$ which means $S_0=V\left(C_{sm}\right)$ and this set is unique. The process goes as follows:

• $t=0$: We convert the vertices of $S_0=V\left(C_{sm}\right)$.

• $t=1:$ The conversion spreads to $v_{sm+1}$.

The process succeeds and $J_{s,m}$ is entirely converted by the end of step 2 which means that $C_k\left(J_{s,m}\right)\le sm$, since $S_0$ is unique and none of its vertices can be removed, we conclude that $C_k\left(J_{s,m}\right)=sm$.

2.2 $C_k\left(P_m⊠P_n\right)$

In this sub-section we determine $C_k\left(G\right)$ for strong grids $P_2⊠P_n$ when $k=\mathrm{4,5}.$ Then we determine $C_2\left(G\right)$ for $P_n⊠P_n$ when $n$ is arbitrary.

Theorem 2.4.

For $n\ge 3;C_4\left(P_2⊠P_n\right)=\{\begin{array}{l}n+1ifnisodd;\\ n+2ifniseven.\end{array}$

Proof.

Let $P_2⊠P_n$ be a strong grid graph on which an irreversible 4-threshold conversion process is being studied with a seed set $S_0$, let $U\subseteq V-S_0$ and $\left\{\left(\mathrm{1,1}\right),\left(1,n\right),\left(\mathrm{2,1}\right),\left(2,n\right)\right\}\cap U=\varnothing$, then $U$ is a 2-unconvertible set of $P_2⊠P_n$ if it satisfies the following condition:

$\text{For}\text{all}u\in U:\left|N\left(u\right)\cap U\right|\ge 2.$

Which means each vertex $u\in U$ is unconverted and is adjacent to at least $2$ vertices of $U$ at $t=0$. Since $\mathrm{d}\mathrm{e}\mathrm{g}\left(u\right)=5$ then $\left|N\left(u\right)\cap S_0\right|\le 3$ and the conversion cannot reach any vertex of $U$ during any step of the process. Therefore, we try to avoid having any version of $U$ on $P_2⊠P_n$ when choosing $S_0$. For $2\le j\le n-1$, we imply that the following sets are 4-unconvertible:

$X_1=\left\{\left(1,j-1\right),\left(1,j\right),\left(2,j\right)\right\}$, $X_2=\left\{\left(2,j-1\right),\left(1,j\right),\left(2,j\right)\right\}$, $X_3=\left\{\left(1,j\right),\left(2,j\right),\left(1,j+1\right)\right\}$, $X_4=\left\{\left(1,j\right),\left(2,j\right),\left(2,j+1\right)\right\}$. Figure 5 shows that for $1\le i\le 4$: if $X_i\cap S_0=\mathit{\varnothing }$ on $P_2⊠P_6$ then none of the vertices of $X_i$ can be converted and the process fails even if $S_0=V-X_i$. In order to avoid having any version of $X_1,X_2,X_3$ or $X_4$ on $P_2⊠P_n$, every two adjacent columns must include at least two vertices of $S_0$ at $t=0$.

We consider the following cases:

Case 1. $n$ is odd.

Let $S_0$ be a seed set of an irreversible 4-threshold conversion process on $P_2⊠P_n,$ since each vertex of $W=\left\{\left(\mathrm{1,1}\right),\left(1,n\right),\left(\mathrm{2,1}\right),\left(2,n\right)\right\}$ is of degree 3, then $W\subset S_0$, otherwise the process fails. Since we are trying to avoid having two adjacent columns that include less than two vertices of $S_0$ at $t=0$, we choose $S_0=\left\{\left(\mathrm{1,2}l+1\right),\left(\mathrm{2,2}l+1\right):0\le l\le \frac{n-1}{2}\right\}$, which means $S_0$ contains all the vertices of the odd indexed columns of $P_2⊠P_n$ and $\left|S_0\right|=n+1$. The process goes as follows:

$t=0:S_0=\left\{\left(\mathrm{1,2}l+1\right),\left(\mathrm{2,2}l+1\right):0\le l\le \frac{n-1}{2}\right\}\text{.}$

$t=1:S_1=S_0\cup \left\{\left(\mathrm{1,2}l\right),\left(\mathrm{2,2}l\right):1\le l\le \frac{n-1}{2}\right\}=V\left(P_2⊠P_n\right)\text{.}$

This means $S_0$ is an I4CS on $P_2⊠P_n$. Therefore, if $n$ is odd then:

(3)$C_4\left(P_2⊠P_n\right)\le n+1$

Figure 6 illustrates that $C_4\left(P_2⊠P_9\right)\le 10$.

Now let us assume that $D_0$ is a 4-conversion seed set of cardinality $n$ on $P_2⊠P_n$. Since $W$ must be contained in $D_0$, this means we need to distribute the remaining $n-4$ vertices of $D_0$ on the remaining $n-2$ columns $\left(\mathrm{2,3},\dots ,n-1\right)$ without having two adjacent columns that include less than two vertices of $D_0$ which is impossible. Therefore, we end up with at least one version of $X_1,X_2,X_3$ or $X_4$ on $P_2⊠P_n$ and the process fails. This means if $n$ is odd:

(4)$C_4\left(P_2⊠P_n\right)>n$

From (3) and (4) we conclude that $C_4\left(P_2⊠P_n\right)=n+1$ if $n$ is odd.

Case 2. $n$ is even.

In a similar way to Case 1, the vertices of $W$ must be contained in the seed set $S_0$. We choose $S_0=\left\{\left(\mathrm{1,2}l+1\right),\left(\mathrm{2,2}l+1\right):0\le l\le \frac{n}{2}-1\right\}\cup \left\{\left(1,n\right),\left(2,n\right)\right\}$ which is of cardinality $n+2$. The process goes as follows:

$t=0:S_0=\left\{\left(\mathrm{1,2}l+1\right),\left(\mathrm{2,2}l+1\right):0\le l\le \frac{n}{2}-1\right\}\cup \left\{\left(1,n\right),\left(2,n\right)\right\}\text{.}$

$t=1:S_1=S_0\cup \left\{\left(\mathrm{1,2}l\right),\left(\mathrm{2,2}l\right):1\le l\le \frac{n}{2}-1\right\}=V\left(P_2⊠P_n\right)\text{.}$

This means $S_0$ is an I4CS on $P_2⊠P_n$. Therefore, if $n$ is even then:

(5)$C_4\left(P_2⊠P_n\right)\le n+2$

Figure 7 shows that $C_4\left(P_2⊠P_{10}\right)\le 12$. According to the same 4-threshold conversion process, let $D_0$ be an I4CS of cardinality $n+1$. Since $W$ must be contained in $D_0$, it is impossible to distribute the remaining $n-3$ vertices of $D_0$ on the $n-2$ unconverted columns at $t=0$ without having at least two adjacent columns that include less than two vertices of $D_0$, which means a version of $X_1,X_2,X_3$ or $X_4$ will definitely be created on $P_2⊠P_n$ and the process fails. We conclude that if $n$ is even then:

(6)$C_4\left(P_2⊠P_n\right)>n+1$

From (5) and (6) we conclude that $C_4\left(P_2⊠P_n\right)=n+2$ if $n\ge 4$ and $n$ is even. From Case 1 and Case 2 we conclude the requested.

Theorem 2.5.

For $n\ge 3;C_5\left(P_2⊠P_n\right)=\{\begin{array}{l}\frac{3n+1}{2}ifnisodd;\\ \frac{3n}{2}+1ifniseven.\end{array}$

Proof.

In a similar way to Theorem 2.4, the vertices of $W=\left\{\left(\mathrm{1,1}\right),\left(1,n\right),\left(\mathrm{2,1}\right),\left(2,n\right)\right\}$ must be included in the seed set $S_0$. Now we try to determine which vertices of $M=V-W$ we need to include in $S_0$. Since $M=\left\{\left(1,j\right),\left(2,j\right):2\le j\le n-1\right\}$, every vertex of $M$ is of degree 5 which means there cannot be two adjacent vertices $v_1,v_2\in M-S_0$. Otherwise, the process will fail because neither $v_1\text{nor}{v}_2$ will be converted at any step of the conversion process. We conclude that $M-S_0$ must be an independent set. In order to make $S_0$ as small as possible, we try to make $M-S_0$ as large as possible. We notice that $M$ represents the vertices of a strong grid $P_2⊠P_{n-2}$ with the difference that the end vertices of $M$: $\left(\mathrm{1,2}\right),\left(\mathrm{2,2}\right),\left(1,n-1\right)$, $\left(2,n-1\right)$ are of degree 5 while the end vertices of a usual $P_2⊠P_{n-2}$ strong grid: $\left(\mathrm{1,1}\right),\left(\mathrm{2,1}\right),\left(1,n\right)$, $\left(2,n\right)$ are of degree 3, but this difference does not change that $\alpha \left(G_M\right)=\alpha \left(P_2⊠P_{n-2}\right)$ which means from Proposition 1.5, $\alpha \left(G_M\right)=\frac{n-2}{2}$. We conclude that the minimum cardinality of $S_0$ that does not allow having two adjacent unconverted vertices is:

$\left|S_0\right|=\left|M\right|-\alpha \left(G_M\right)+\left|W\right|=2\left(n-2\right)-\frac{n-2}{2}+4=2n-\frac{n-2}{2}$. We consider the following cases for $n:$

Case 1. $n$ is odd.

Since $n$ is odd then $\alpha \left(G_M\right)=\frac{n-1}{2}$. Therefore, $C_5\left(P_2⊠P_n\right)=2n-\frac{n-1}{2}=\frac{3n+1}{2}$.

Case 2. $n$ is even.

Since $n$ is even then $\alpha \left(G_M\right)=\frac{n-2}{2}$. Therefore, $C_5\left(P_2⊠P_n\right)=2n-\frac{n-2}{2}=\frac{3n}{2}+1$.

From Case 1 and case 2 we conclude the requested.

Theorem 2.6.

For $n\ge 3;C_2\left(P_n⊠P_n\right)=2$.

Proof.

It is known by definition that $C_k\left(G\right)\ge k$ for any $G$. Therefore, $C_2(P_n⊠P_n)\ge 2$. Now we prove that $C_2(P_n⊠P_n)\le 2$ by finding an I2CS of cardinality 2 on $P_n⊠P_n$. In order to make the conversion steps as few as possible, we start from the middle by choosing the seed set to be $S_0=\left\{\left(\frac{n-1}{2},\frac{n+1}{2}\right),\left(\frac{n+3}{2},\frac{n+1}{2}\right)\right\}$. The process goes as follows:

$t=0:S_0=\left\{\left(\frac{n-1}{2},\frac{n+1}{2}\right),\left(\frac{n+3}{2},\frac{n+1}{2}\right)\right\}\text{.}$

$t=1:S_1=S_0\cup \left\{\left(\frac{n+1}{2},\frac{n-1}{2}\right),\left(\frac{n+1}{2},\frac{n+1}{2}\right),\left(\frac{n+1}{2},\frac{n+3}{2}\right)\right\}\text{.}$

$t=2:S_2=S_1\cup \left\{\left(\frac{n-1}{2},\frac{n-1}{2}\right),\left(\frac{n-1}{2},\frac{n+3}{2}\right),\left(\frac{n+3}{2},\frac{n-1}{2}\right),\left(\frac{n+3}{2},\frac{n+3}{2}\right)\right\}\text{.}$

$\begin{array}{l}t=3:S_3=S_2\cup \{\left(\frac{n-3}{2},\frac{n-1}{2}\right),\left(\frac{n-3}{2},\frac{n+1}{2}\right),\left(\frac{n-3}{2},\frac{n+3}{2}\right),\left(\frac{n-1}{2},\frac{n-3}{2}\right),\\ \left(\frac{n+1}{2},\frac{n-3}{2}\right),\left(\frac{n+3}{2},\frac{n-3}{2}\right),\left(\frac{n+5}{2},\frac{n-1}{2}\right),\left(\frac{n+5}{2},\frac{n+1}{2}\right),\left(\frac{n+5}{2},\frac{n+3}{2}\right),\\ \left(\frac{n-1}{2},\frac{n+5}{2}\right),\left(\frac{n+1}{2},\frac{n+5}{2}\right),\left(\frac{n+3}{2},\frac{n+5}{2}\right)\}\text{.}\end{array}$

$\begin{array}{l}t=4:S_4=S_3\cup \{\left(\frac{n-5}{2},\frac{n-1}{2}\right),\left(\frac{n-5}{2},\frac{n+1}{2}\right),\left(\frac{n-5}{2},\frac{n+3}{2}\right),\left(\frac{n-1}{2},\frac{n-5}{2}\right),\\ \left(\frac{n+1}{2},\frac{n-5}{2}\right),\left(\frac{n+3}{2},\frac{n-5}{2}\right),\left(\frac{n+7}{2},\frac{n-1}{2}\right),\left(\frac{n+7}{2},\frac{n+1}{2}\right),\left(\frac{n+7}{2},\frac{n+3}{2}\right),\\ \left(\frac{n-1}{2},\frac{n+7}{2}\right),\left(\frac{n+1}{2},\frac{n+7}{2}\right),\left(\frac{n+3}{2},\frac{n+7}{2}\right),\left(\frac{n-3}{2},\frac{n-3}{2}\right),\\ \left(\frac{n-3}{2},\frac{n+5}{2}\right),\left(\frac{n+5}{2},\frac{n-3}{2}\right),\left(\frac{n+5}{2},\frac{n+5}{2}\right)\}\text{.}\end{array}$

$\begin{array}{l}5\le t\le \frac{n+1}{2}:S_t=S_{t-1}\cup \{\left(\frac{n-2t+3}{2},\frac{n-1}{2}\right),\left(\frac{n-2t+3}{2},\frac{n+1}{2}\right),\\ \left(\frac{n-2t+3}{2},\frac{n+3}{2}\right),\left(\frac{n-1}{2},\frac{n-2t+3}{2}\right),\left(\frac{n+1}{2},\frac{n-2t+3}{2}\right),\left(\frac{n+3}{2},\frac{n-2t+3}{2}\right),\\ \left(\frac{n+2t-1}{2},\frac{n-1}{2}\right),\left(\frac{n+2t-1}{2},\frac{n+1}{2}\right),\left(\frac{n+2t-1}{2},\frac{n+3}{2}\right),\left(\frac{n-1}{2},\frac{n+2t-1}{2}\right),\\ \left(\frac{n+1}{2},\frac{n+2t-1}{2}\right),\left(\frac{n+3}{2},\frac{n+2t-1}{2}\right),\left(\frac{n-2l+5}{2},\frac{n-2t+2l-3}{2}\right),\\ \left(\frac{n-2t+2l-3}{2},\frac{n+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n-2t+2l-3}{2}\right),\\ \left(\frac{n+2l-3}{2},\frac{n+2t-2l+5}{2}\right):4\le l\le t\}\text{.}\end{array}$

We notice that at $t=\frac{n+1}{2}$, the spread reaches its limits horizontally and vertically (the three middle vertices of each of the first row, the last row, the first column and the last column are converted). Therefore, in the remaining steps, the conversion spreads only diagonally as follows:

$t=\frac{n+1}{2}+1:S_{\frac{n+1}{2}+1}=S_{\frac{n+1}{2}}\cup \left\{\left(\frac{n-2l+5}{2},\frac{n-2t+2l-3}{2}\right),\left(\frac{n-2t+2l-3}{2},\frac{n+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n-2t+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n+2t-2l+5}{2}\right):4\le l\le t\right\}\text{.}$

$t=\frac{n+1}{2}+2\text{:}{S}_{\frac{n+1}{2}+2}=S_{\frac{n+1}{2}+1}\cup \left\{\left(\frac{n-2l+5}{2},\frac{n-2t+2l-3}{2}\right),\left(\frac{n-2t+2l-3}{2},\frac{n+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n-2t+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n+2t-2l+5}{2}\right):5\le l\le t-1\right\}\text{.}$

For $2\le m\le \frac{n-3}{2}\text{which}\text{means}\text{for}\frac{n+1}{2}+2\le t\le n-1$:

$S_{\frac{n+1}{2}+m}=S_{\frac{n+1}{2}+m-1}\cup \left\{\left(\frac{n-2l+5}{2},\frac{n-2t+2l-3}{2}\right),\left(\frac{n-2t+2l-3}{2},\frac{n+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n-2t+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n+2t-2l+5}{2}\right):m+3\le l\le t-m+1\right\}\text{.}$

When we reach step $t=n-1$, we have $m=\frac{n-3}{2}$ which means:

$\begin{array}{l}{S}_{n-1}=S_{n-2}\cup \{\left(\frac{n-2l+5}{2},\frac{n-2\left(n-1\right)+2l-3}{2}\right),\left(\frac{n-2\left(n-1\right)+2l-3}{2},\frac{n+2l-3}{2}\right),\\ \left(\frac{n+2l-3}{2},\frac{n-2\left(n-1\right)+2l-3}{2}\right),\left(\frac{n+2l-3}{2},\frac{n+2\left(n-1\right)-2l+5}{2}\right):\frac{n+3}{2}\le l\le \frac{n+3}{2}\}\\ =S_{n-2}\cup \{\left(\mathrm{1,1}\right),\left(1,n\right),\left(n,1\right),\left(n,n\right)\}=V\left(P_n⊠P_n\right)\end{array}$

we conclude that $S_0$ is an I2CS of cardinality 2 on $P_n⊠P_n$. Therefore, $C_2(P_n⊠P_n)\le 2$ which means $C_2(P_n⊠P_n)=2$ if $n$ is odd. Figure 8 illustrates that $C_2(P_9⊠P_9)=2.$

Case 2. $n$ is even.

In a similar way to Case 1, we need to prove that $C_2(P_n⊠P_n)\le 2$by finding an I2CS of cardinality 2 on $P_n⊠P_n$. We start from the middle to make the conversion steps as few as possible. We choose the seed set to be $S_0=\left\{\left(\frac{n}{2},\frac{n}{2}\right),\left(\frac{n}{2}+1,\frac{n}{2}+1\right)\right\}$. The process goes as follows:

$t=0:S_0=\left\{\left(\frac{n}{2},\frac{n}{2}\right),\left(\frac{n}{2}+1,\frac{n}{2}+1\right)\right\}\text{.}$

$t=1:S_1=S_0\cup \left\{\left(\frac{n}{2},\frac{n}{2}+1\right),\left(\frac{n}{2}+1,\frac{n}{2}\right)\right\}\text{.}$

$t=2:S_2=S_1\cup \left\{\left(\frac{n}{2}-1,\frac{n}{2}\right),\left(\frac{n}{2}-1,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}-1\right),\left(\frac{n}{2}+1,\frac{n}{2}-1\right),\left(\frac{n}{2}+2,\frac{n}{2}\right),\left(\frac{n}{2}+2,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}+2\right),\left(\frac{n}{2}+1,\frac{n}{2}+2\right)\right\}\text{.}$

$t=3:S_3=S_2\cup \left\{\left(\frac{n}{2}-2,\frac{n}{2}\right),\left(\frac{n}{2}-2,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}-2\right),\left(\frac{n}{2}+1,\frac{n}{2}-2\right),\left(\frac{n}{2}+3,\frac{n}{2}\right),\left(\frac{n}{2}+3,\frac{n}{2}\right),\left(\frac{n}{2},\frac{n}{2}+3\right),\left(\frac{n}{2}+1,\frac{n}{2}+3\right),\left(\frac{n}{2}-1,\frac{n}{2}-1\right),\left(\frac{n}{2}+2,\frac{n}{2}-1\right),\left(\frac{n}{2}+2,\frac{n}{2}+2\right),\left(\frac{n}{2}-1,\frac{n}{2}+2\right)\right\}\text{.}$

$t=4:S_4=S_3\cup \left\{\left(\frac{n}{2}-3,\frac{n}{2}\right),\left(\frac{n}{2}-3,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}-3\right),\left(\frac{n}{2}+1,\frac{n}{2}-3\right),\left(\frac{n}{2}+4,\frac{n}{2}\right),\left(\frac{n}{2}+4,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}+4\right),\left(\frac{n}{2}+1,\frac{n}{2}+4\right),\left(\frac{n}{2}-2,\frac{n}{2}-1\right),\left(\frac{n}{2}-1,\frac{n}{2}-2\right),\left(\frac{n}{2}+3,\frac{n}{2}-1\right),\left(\frac{n}{2}+2,\frac{n}{2}-2\right),\left(\frac{n}{2}-2,\frac{n}{2}+2\right),\left(\frac{n}{2}-1,\frac{n}{2}+3\right)\right\}\text{.}$

$2\le t\le \frac{n}{2}:S_t=S_{t-1}\cup \left\{\left(\frac{n}{2}-t+1,\frac{n}{2}\right),\left(\frac{n}{2}-t+1,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}-t+1\right),\left(\frac{n}{2}+1,\frac{n}{2}-t+1\right),\left(\frac{n}{2}+t,\frac{n}{2}\right),\left(\frac{n}{2}+t,\frac{n}{2}+1\right),\left(\frac{n}{2},\frac{n}{2}+t\right),\left(\frac{n}{2}+1,\frac{n}{2}+t\right),\left(\frac{n}{2}-l+2,\frac{n}{2}-t+l-1\right),\left(\frac{n}{2}+l-1,\frac{n}{2}-t+l-1\right),\left(\frac{n}{2}-t+l-1,\frac{n}{2}+l-1\right),\left(\frac{n}{2}+l-1,\frac{n}{2}+t-l+2\right):3\le l\le t\right\}\text{.}$

We notice that at $t=\frac{n}{2}\text{,}$ the spread reaches its limits horizontally and vertically (the three middle vertices of each of the first row, the last row, the first column and the last column are converted). Therefore, in the remaining steps, the conversion spreads only diagonally as follows:

For $1\le m\le \frac{n}{2}-1\text{which}\text{means}\text{for}\frac{n+1}{2}+1\le t\le n-1$:

$S_{\frac{n}{2}+m}=S_{\frac{n}{2}+m-1}\cup \left\{\left(\frac{n}{2}-l+2,\frac{n}{2}-t+l-1\right),\left(\frac{n}{2}+l-1,\frac{n}{2}-t+l-1\right),\left(\frac{n}{2}-t+l-1,\frac{n}{2}+l-1\right),\left(\frac{n}{2}+l-1,\frac{n}{2}+t-l+2\right):m+2\le l\le t-m+1\right\}\text{.}$

When we reach step $t=n-1$, we have $m=\frac{n}{2}-1$ which means $l=\frac{n}{2}+1$ therefore:

$S_{n-1}=S_{\frac{n}{2}+\frac{n}{2}-1}=S_{\frac{n}{2}+\frac{n}{2}-2}\cup \{\left(\frac{n}{2}-\left(\frac{n}{2}+1\right)+2,\frac{n}{2}-\left(n-1\right)+\left(\frac{n}{2}+1\right)-1\right),\left(\frac{n}{2}+\left(\frac{n}{2}+1\right)-1,\frac{n}{2}-\left(n-1\right)+\left(\frac{n}{2}+1\right)-1\right),\left(\frac{n}{2}-\left(n-1\right)+\left(\frac{n}{2}+1\right)-1,\frac{n}{2}+\left(\frac{n}{2}+1\right)-1\right),\left(\frac{n}{2}+\left(\frac{n}{2}+1\right)-1,\frac{n}{2}+\left(n-1\right)-\left(\frac{n}{2}+1\right)+2\right)\}=S_{\frac{n}{2}+\frac{n}{2}-2}\cup \left\{\left(\mathrm{1,1}\right),\left(n,1\right),\left(1,n\right),\left(n,n\right)\right\}=V\left(P_n⊠P_n\right)\text{.}$

We conclude that $S_0$ is an I2CS and $C_2(P_n⊠P_n)\le 2$ which means $C_2(P_n⊠P_n)=2$ if $n$ is even. Figure 9 illustrates that $C_2\left(P_8⊠P_8\right)=2.$ From Case 1 and Case 2 we conclude the requested.

Figures

Figure 1

$A_1=\left\{a,b,c\right\},B_1=\left\{x,y\right\}$ are 2-unconvertible on $J_{s,m}$

Figure 2

$C_2\left(J_{\mathrm{6,4}}\right)\le 11$

Figure 3

$C_2\left(J_{\mathrm{6,4}}\right)>10$

Figure 4

A 2-conversion process on $J_{\mathrm{7,4}}$ starting with $\left|S_0\right|=13$

Figure 5

$X_1,X_2,X_3$ and $X_4$ are 4-unconvertible on $P_2⊠P_6$

Figure 6

$C_4\left(P_2⊠P_9\right)\le 10$

Figure 7

$C_4\left(P_2⊠P_{10}\right)\le 12$

Figure 8

$C_2\left(P_9⊠P_9\right)=2$

Figure 9