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=|V| and m=|E| denote the numbers of vertices and edges at a graph G(V,E), respectively. Let Y⊆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=(Y,F) is called an induced subgraph of G by Y and is denoted by GY. The open neighborhood of a vertex v∈V is N(v)={u∈V:uv∈E} while the closed neighborhood of v is N[v]=N(v)∪{v}. The degree of a vertex v is denoted by deg(v) and deg(v)=|N(v)|. An independent vertex set of a graph G(V,E) is a subset of V such that no two vertices in the subset represent and edge of G. The independence number, denoted by α(G), 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 S0⊆V, and for each step t(t=1,2,…,), St is obtained from St−1 by adjoining all vertices that have at least k neighbors in St−1.We call S0 the seed set of the k-threshold conversion process and if St=V(G) for some t≥0, then S0 is an irreversible k-threshold conversion set (IkCS) of G. The k-threshold conversion number of G (denoted by Ck(G)) is the minimum cardinality of all the IkCSs of G. It is obvious that 1≤k≤Δ(G) and C1(G)=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 C2(G) for paths and cycles. They also determined C2(G) and C3(G) for grid graphs P3⊠Pn. In Ref. [2] Kynčl et al. found an upper bound for Ck(G) of toroidal grids of size m×n if m=4 or n=4. In Ref. [3] Adams et al. presented an upper bound for Ck(G) of the tensor product of two arbitrary graphs G and H. In Ref. [4] Mynhardt and Wodlinger presented a lower bound for Ck(G) of graphs of maximum degree k+1. Frances et al. [5] studied the relationship between IkCSs and minimum decycling sets. An upper bound for Ck(G) 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 C2(G) and C3(G) for the strong grid graphs Pm⊠Pn when m=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 Js,m for m≥2 is a graph on sm+1vertices, i.e. a graph consisting of a cycle Csmwith one additional vertex which is adjacent to m vertices of Csm at distance s from each other on Csm, see Ref. [12] for more information on Jahangir graph. Let vsm+1 be the label of the central vertex and v1,v2,…,vsm be the labels of the vertices that incident clockwise on cycle Csm so that deg(v1)=3. We will use this labeling for the rest of the article. The vertices that are adjacent to vsm+1 have the labels v1,v1+s,v1+2s,…v1+(m−1)s. Let Pm, Pn be two paths, we define the strong product of Pm and Pn (also called strong grid graph) as the graph Pm⊠Pn such that V(Pm⊠Pn)={(i,j):1≤i≤m, 1≤j≤n} and two vertices (i1,j1), (i2,j2) are adjacent if and only if max{|i2−i1|,|j2−j1|}=1. See Ref. [13] for more information on strong grids.

Proposition 1.1.

[3] For n≥2;  C2(Pn)=n+12.

Proposition 1.2.

[3] For n≥3;  C2(Cn)=n2.

Proposition 1.3.

[13] For n≥2;  C2(P2⊠Pn)=2.

Proposition 1.4.

[13] For n≥2;  C3(P2⊠Pn)=n+1.

Proposition 1.5.

[6] For m,n≥2;  α(Pm⊠Pn)=m2n2.

• Note 1: As an immediate consequence of the definition, Ck(G)≥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(V,E) all vertices {v∈V ; deg(v)<k} must be included in the seed set S0, otherwise the process will fail because none of these vertices can satisfy the conversion rule.

• Note 3: For Jahangir graph Js,m, we denote the set of vertices of degree 3 which consists of v1,v1+s,…v1+(m−1)s by R. So, R={v1+is :i=0,1,…,m−1}.

• 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 Ck(G) for generalized Jahangir graph Js,m for 1<k≤m and s,m are arbitraries. We also determine Ck(G) for strong grids P2⊠Pn when k=4,5. Then we determine C2(G) for Pn⊠Pn when n is arbitrary.

2.1 Ck(Js, m)

In this sub-section we find Ck(G) of generalized Jahangir graph Js,m for 1<k≤m and s,m are arbitraries.

Theorem 2.1.

For s,m≥2, C2(Js, m)=m(s−1)2+1.

Proof.

Let Js, m be a Jahangir graph on which an irreversible 2-threshold conversion process is being studied with a seed set S0, let U⊆V−S0 and vsm+1∉U, then U is a 2-unconvertible set of Js, m if it satisfies the following condition:

For all u∈U: |N(u)∩U|≥2.

Which means each vertex u∈U is unconverted and is adjacent to at least 2 vertices of U at t=0. Since deg(u)≤3 then |N(u)∩S0|<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 Js, mwhen choosing S0. We imply that the following sets A1={a,b,c} with (deg(a)=deg(c)=2 and deg(b)=3), B1={x,y} (with deg(x)=deg(y)=2) are 2-unconvertible sets on Js, m. Both A1 and B1 are represented in Figure 1.

By Proposition 1.1, we have C2(Pn)=n+12. It is obvious that the n+12−IkCS of a path Pn must contain the end vertices {v1,vn} otherwise the spread will never reach them. The vertices of R divide Csm 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:

Ps−1(1)=v2…vs,Ps−1(2)=v2+s…v2s,⋮Ps−1(m)=v2+(m−1)s…vms.

We consider the following subcases:

Case 1. s is even.

In this case, each path Ps−1(i):1≤i≤m contains an odd number of vertices. We divide V(Ps−1(i)) into two sets:

EPi={v2+(i−1)s,v4+(i−1)s,…,vis} which consists of s−12 vertices.

OPi={∅   if s=2;{v3+(i−1)s,v5+(i−1)s,…,vis−1} which consists of s−12 vertices if s≥4.

We define a family of sets D={Di:1≤i≤m, where Di={EPi if i is odd;OPi if i is even.}

The process goes as follows:

• t=0: We convert the vertices of S0=D∪{vsm+1}.

• t=1: The conversion spreads to:

  • The vertices of {OPi:i is odd}..

  • The vertices of {EPi−{v2+(i−1)s, vis}:i is even}..

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

• t=2: The conversion spreads to {v2+(i−1)s, vis:i is even}..

By the end of step t=2, the conversion is spread to V( Js, m) entirely and the process succeeds. It is obvious that |S0|={m2(s−12+s−12)+1 if m is even;m2s−12+m2s−12+1 if m is odd.

Which means:

(1)C2(Js, m)≤m(s−1)2+1

Figure 2 shows that C2( J6,4)≤11.

We imply that the sets A1={a,b,c}, B1={x,y} represented in Figure 1 are 2-unconvertible on Js, m. We notice that D is the only m(s−1)2 - seed set that does not leave any versions of A1 or B1 on Csm and every k-seed set with k<m(s−1)2 will leave some versions of A1 or B1 on Csm. Let us assume that D0 is a IkCS of cardinality m(s−1)2, we consider the following subcases:

Case 1.a. vsm+1∉D0, which means D0⊆V(Csm), and since |D0|=m(s−1)2, then D0=D as we found earlier. However, since C2(Csm)=sm2 by Proposition 1.2, it is impossible to convert all the vertices of Csm depending only on D. Therefore, we need to convert vsm+1 at some point and benefit from it being adjacent to m vertices of Csm. To achieve that we need at step t=0 to choose one of three strategies:

• Convert 2 vertices of R (e.g. v1,v1+s). However, that leaves m(s−1)2−2 vertices in D0 which means we end up with at least two versions of B1 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. v1), and 2 vertices that are adjacent to a vertex of R (for example v2s,v2+2s), by converting the remaining m(s−1)2−3 vertices in D0 in a similar way to D, we end up with two versions of B1 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 (e.g.v2,vsm,vs,v2+s), by converting the remaining m(s−1)2−4 vertices in D0 in a similar way to D, we end up with two versions of B1 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 B1 on Csm, 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 C2(Js, m)>m(s−1)2 when s is even and vsm+1∉D0.

Case 1.b. vsm+1∈D0, by converting m(s−1)2 vertices of Csm we end up with two versions of B1 (as shown in Figure 3(d)), and the process fails. Therefore, C2(Js, m)>m(s−1)2 in this case as well.

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

(2)For s is even, C2(Js, m)>m(s−1)2.

From (1) and (2) we conclude that for s is even; C2(Js, m)=m(s−1)2+1.

Case 2. s is odd.

In this case, each path Ps−1(i):1≤i≤m contains an even number of vertices. We define a family of sets D={Di:1≤i≤m} where Di={v2+(i−1)s,v4+(i−1)s,…,vis−1} which contains m(s−1)2 vertices. The process goes as follows:

1. t=0: We convert the vertices of S0=D∪{vsm+1}.

2. t=1: The conversion spreads to the vertices of {Di−{vis−1}:1≤i≤m}.

3. t=2: The conversion spreads to {vis−1:1≤i≤m}.

By the end of step t=2, the conversion is spread to V(Js, m) entirely and the process succeeds.

It is obvious that |S0|=m(s−1)2+1 which means C2(Js, m)≤m(s−1)2+1. In a similar way to Case 1, S0 is the only IkCS of cardinality m(s−1)2+1 because D is the only set of cardinality m(s−1)2 that does not leave any versions of A1 or B1 on Csm. By following the same discussion in Case 1 we conclude that C2(Js, m)>m(s−1)2 if s is odd, which means C2(Js, m)=m(s−1)2+1 if s is odd.

Figure 4 illustrates a 2-conversion process on J7,4 starting with |S0|=13.

From Case 1 and Case 2 we conclude that C2(Js, m)=m(s−1)2+1 for s≥2.

Theorem 2.2.

For m≥2, C3(Js, m)=m(s−1)+1.

Proof.

By definition all vertices with degree lower than 3 need to be added to the seed set S0. 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 vsm+1 is initially converted. The process goes as follows:

• t=0: We convert the vertices of S0={V(Csm)−R}∪{vsm+1}, we implied that this set is unique.

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

The process succeeds and Js, m is entirely converted by the end of step 2 which means that C3(Js, m)≤m(s−1)+1, since S0 is unique and none of its vertices can be removed, then C3(Js, m)=m(s−1)+1.

Theorem 2.3.

For 4≤k≤m, Ck(Js, m)=sm.

Proof.

By definition all vertices with degree lower than 4 need to be included in S0 which means S0=V(Csm) and this set is unique. The process goes as follows:

• t=0: We convert the vertices of S0=V(Csm).

• t=1: The conversion spreads to vsm+1.

The process succeeds and Js, m is entirely converted by the end of step 2 which means that Ck(Js, m)≤sm, since S0 is unique and none of its vertices can be removed, we conclude that Ck(Js, m)=sm.

2.2 Ck(Pm⊠Pn)

In this sub-section we determine Ck(G) for strong grids P2⊠Pn when k=4,5. Then we determine C2(G) for Pn⊠Pn when n is arbitrary.

Theorem 2.4.

For n≥3; C4(P2⊠Pn)={n+1 if n is odd;  n+2 if n is even.

Proof.

Let P2⊠Pn be a strong grid graph on which an irreversible 4-threshold conversion process is being studied with a seed set S0, let U⊆V−S0 and {(1,1),(1,n),(2,1),(2,n)}∩U=∅, then U is a 2-unconvertible set of P2⊠Pn if it satisfies the following condition:

For all u∈U: |N(u)∩U|≥2.

Which means each vertex u∈U is unconverted and is adjacent to at least 2 vertices of U at t=0. Since deg(u)=5 then |N(u)∩S0|≤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 P2⊠Pn when choosing S0. For 2≤j≤n−1, we imply that the following sets are 4-unconvertible:

X1={(1,j−1),(1,j),(2,j)}, X2={(2,j−1),(1,j),(2,j)}, X3={(1,j),(2,j),(1,j+1)}, X4={(1,j),(2,j),(2,j+1)}. Figure 5 shows that for 1≤i≤4: if Xi∩S0=∅ on P2⊠P6 then none of the vertices of Xi can be converted and the process fails even if S0=V−Xi. In order to avoid having any version of X1,X2,X3 or X4 on P2⊠Pn, every two adjacent columns must include at least two vertices of S0 at t=0.

We consider the following cases:

Case 1. n is odd.

Let S0 be a seed set of an irreversible 4-threshold conversion process on P2⊠Pn, since each vertex of W={(1,1),(1,n),(2,1),(2,n)} is of degree 3, then W⊂S0, otherwise the process fails. Since we are trying to avoid having two adjacent columns that include less than two vertices of S0 at t=0, we choose S0={(1,2l+1),(2,2l+1):0≤l≤n−12}, which means S0 contains all the vertices of the odd indexed columns of P2⊠Pn and |S0|=n+1. The process goes as follows:

t=0: S0={(1,2l+1),(2,2l+1):0≤l≤n−12}.

t=1: S1=S0∪{(1,2l),(2,2l):1≤l≤n−12}=V(P2⊠Pn).

This means S0 is an I4CS on P2⊠Pn. Therefore, if n is odd then:

(3)C4(P2⊠Pn)≤n+1

Figure 6 illustrates that C4(P2⊠P9)≤10.

Now let us assume that D0 is a 4-conversion seed set of cardinality n on P2⊠Pn. Since W must be contained in D0, this means we need to distribute the remaining n−4 vertices of D0 on the remaining n−2 columns (2,3,…,n−1) without having two adjacent columns that include less than two vertices of D0 which is impossible. Therefore, we end up with at least one version of X1,X2,X3 or X4 on P2⊠Pn and the process fails. This means if n is odd:

(4)C4(P2⊠Pn)>n

From (3) and (4) we conclude that C4(P2⊠Pn)=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 S0. We choose S0={(1,2l+1),(2,2l+1):0≤l≤n2−1}∪{(1,n),(2,n)} which is of cardinality n+2. The process goes as follows:

t=0: S0={(1,2l+1),(2,2l+1):0≤l≤n2−1}∪{(1,n),(2,n)}.

t=1: S1=S0∪{(1,2l),(2,2l):1≤l≤n2−1}=V(P2⊠Pn).

This means S0 is an I4CS on P2⊠Pn. Therefore, if n is even then:

(5)C4(P2⊠Pn)≤n+2

Figure 7 shows that C4(P2⊠P10)≤12. According to the same 4-threshold conversion process, let D0 be an I4CS of cardinality n+1. Since W must be contained in D0, it is impossible to distribute the remaining n−3 vertices of D0 on the n−2 unconverted columns at t=0 without having at least two adjacent columns that include less than two vertices of D0, which means a version of X1,X2,X3 or X4 will definitely be created on P2⊠Pn and the process fails. We conclude that if n is even then:

(6)C4(P2⊠Pn)>n+1

From (5) and (6) we conclude that C4(P2⊠Pn)=n+2 if n≥4 and n is even. From Case 1 and Case 2 we conclude the requested.

Theorem 2.5.

For n≥3; C5(P2⊠Pn)={3n+12 if n is odd;3n2+1 if n is even.

Proof.

In a similar way to Theorem 2.4, the vertices of W={(1,1),(1,n),(2,1),(2,n)} must be included in the seed set S0. Now we try to determine which vertices of M=V−W we need to include in S0. Since M={(1, j),(2, j):2≤j≤n−1}, every vertex of M is of degree 5 which means there cannot be two adjacent vertices v1,v2∈M−S0. Otherwise, the process will fail because neither v1 nor v2 will be converted at any step of the conversion process. We conclude that M−S0 must be an independent set. In order to make S0 as small as possible, we try to make M−S0 as large as possible. We notice that M represents the vertices of a strong grid P2⊠Pn−2 with the difference that the end vertices of M: (1,2),(2,2),(1,n−1), (2,n−1) are of degree 5 while the end vertices of a usual P2⊠Pn−2 strong grid: (1,1),(2,1),(1,n), (2,n) are of degree 3, but this difference does not change that α(GM)=α(P2⊠Pn−2) which means from Proposition 1.5, α(GM)=n−22. We conclude that the minimum cardinality of S0 that does not allow having two adjacent unconverted vertices is:

|S0|=|M|−α(GM)+|W|=2(n−2)−n−22+4=2n−n−22. We consider the following cases for n:

Case 1. n is odd.

Since n is odd then α(GM)=n−12. Therefore, C5(P2⊠Pn)=2n−n−12=3n+12.

Case 2. n is even.

Since n is even then α(GM)=n−22. Therefore, C5(P2⊠Pn)=2n−n−22=3n2+1.

From Case 1 and case 2 we conclude the requested.

Theorem 2.6.

For n≥3; C2(Pn⊠Pn)=2.

Proof.

It is known by definition that Ck(G)≥k for any G. Therefore, C2(Pn⊠Pn)≥2. Now we prove that C2(Pn⊠Pn)≤2 by finding an I2CS of cardinality 2 on Pn⊠Pn. In order to make the conversion steps as few as possible, we start from the middle by choosing the seed set to be S0={(n−12,n+12),(n+32,n+12)}. The process goes as follows:

t=0: S0={(n−12,n+12),(n+32,n+12)}.

t=1: S1=S0∪{(n+12,n−12),(n+12,n+12),(n+12,n+32)}.

t=2: S2=S1∪{(n−12,n−12),(n−12,n+32),(n+32,n−12),(n+32,n+32)}.

t=3: S3=S2∪{(n−32,n−12),(n−32,n+12),(n−32,n+32),(n−12,n−32),(n+12,n−32),(n+32,n−32),(n+52,n−12),(n+52,n+12),(n+52,n+32),(n−12,n+52),(n+12,n+52),(n+32,n+52)}.

t=4: S4=S3∪{(n−52,n−12),(n−52,n+12),(n−52,n+32),(n−12,n−52),(n+12,n−52),(n+32,n−52),(n+72,n−12),(n+72,n+12),(n+72,n+32),(n−12,n+72),(n+12,n+72),(n+32,n+72),(n−32,n−32),(n−32,n+52),(n+52,n−32),(n+52,n+52)}.

5≤t≤n+12: St=St−1∪{ (n−2t+32,n−12),(n−2t+32,n+12),(n−2t+32,n+32),(n−12,n−2t+32),(n+12,n−2t+32),(n+32,n−2t+32),(n+2t−12,n−12),(n+2t−12,n+12),(n+2t−12,n+32),(n−12,n+2t−12),(n+12,n+2t−12),(n+32,n+2t−12), (n−2l+52,n−2t+2l−32),(n−2t+2l−32,n+2l−32),(n+2l−32,n−2t+2l−32),(n+2l−32,n+2t−2l+52):4≤l≤t}.

We notice that at t=n+12, 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=n+12+1: Sn+12+1=Sn+12∪{ (n−2l+52,n−2t+2l−32),(n−2t+2l−32,n+2l−32),(n+2l−32,n−2t+2l−32),(n+2l−32,n+2t−2l+52):4≤l≤t}.

t=n+12+2: Sn+12+2=Sn+12+1∪{ (n−2l+52,n−2t+2l−32),(n−2t+2l−32,n+2l−32),(n+2l−32,n−2t+2l−32),(n+2l−32,n+2t−2l+52):5≤l≤t−1}.

For 2≤m≤n−32 which means for n+12+2≤t≤n−1:

Sn+12+m=Sn+12+m−1∪{(n−2l+52,n−2t+2l−32),(n−2t+2l−32,n+2l−32),(n+2l−32,n−2t+2l−32),(n+2l−32,n+2t−2l+52):m+3≤l≤t−m+1}.

When we reach step t=n−1, we have m=n−32 which means:

Sn−1=Sn−2∪{ (n−2l+52,n−2(n−1)+2l−32),(n−2(n−1)+2l−32,n+2l−32),(n+2l−32,n−2(n−1)+2l−32),(n+2l−32,n+2(n−1)−2l+52):n+32≤l≤n+32}=Sn−2∪{(1,1),(1,n),(n,1),(n,n)}=V(Pn⊠Pn)

we conclude that S0 is an I2CS of cardinality 2 on Pn⊠Pn. Therefore, C2(Pn⊠Pn)≤2 which means C2(Pn⊠Pn)=2 if n is odd. Figure 8 illustrates that C2(P9⊠P9)=2.

Case 2. n is even.

In a similar way to Case 1, we need to prove that C2(Pn⊠Pn)≤2by finding an I2CS of cardinality 2 on Pn⊠Pn. We start from the middle to make the conversion steps as few as possible. We choose the seed set to be S0={(n2,n2),(n2+1,n2+1)}. The process goes as follows:

t=0: S0={(n2,n2),(n2+1,n2+1)}.

t=1: S1=S0∪{(n2,n2+1),(n2+1,n2)}.

t=2: S2=S1∪{(n2−1, n2),(n2−1, n2+1),(n2,n2−1),(n2+1, n2−1),(n2+2, n2),(n2+2, n2+1),(n2,n2+2),(n2+1,n2+2)}.

t=3: S3=S2∪{(n2−2, n2),(n2−2, n2+1),(n2,n2−2),(n2+1, n2−2),(n2+3, n2),(n2+3, n2),(n2,n2+3),(n2+1,n2+3),(n2−1,n2−1),(n2+2,n2−1),(n2+2,n2+2),(n2−1,n2+2)}.

t=4: S4=S3∪{(n2−3, n2),(n2−3, n2+1),(n2,n2−3),(n2+1, n2−3),(n2+4, n2),(n2+4, n2+1),(n2,n2+4),(n2+1,n2+4),(n2−2,n2−1),(n2−1,n2−2),(n2+3,n2−1),(n2+2,n2−2),(n2−2,n2+2),(n2−1,n2+3)}.

2≤t≤n2: St=St−1∪{(n2−t+1, n2), (n2−t+1, n2+1), (n2, n2−t+1), (n2+1,n2−t+1), (n2+t, n2),(n2+t, n2+1),(n2,n2+t),(n2+1,n2+t),(n2−l+2,n2−t+l−1),(n2+l−1,n2−t+l−1),(n2−t+l−1,n2+l−1),(n2+l−1,n2+t−l+2):3≤l≤t}.

We notice that at t=n2, 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≤m≤n2−1 which means for n+12+1≤t≤n−1:

Sn2+m=Sn2+m−1∪{(n2−l+2,n2−t+l−1),(n2+l−1,n2−t+l−1),(n2−t+l−1,n2+l−1),(n2+l−1,n2+t−l+2):m+2≤l≤t−m+1}.

When we reach step t=n−1, we have m=n2−1 which means l=n2+1 therefore:

Sn−1=Sn2+n2−1=Sn2+n2−2∪{(n2−(n2+1)+2,n2−(n−1)+(n2+1)−1),(n2+(n2+1)−1,n2−(n−1)+(n2+1)−1),(n2−(n−1)+(n2+1)−1,n2+(n2+1)−1),(n2+(n2+1)−1,n2+(n−1)−(n2+1)+2)}=Sn2+n2−2∪{(1,1),(n,1),(1,n),(n,n)}=V(Pn⊠Pn).

We conclude that S0 is an I2CS and C2(Pn⊠Pn)≤2 which means C2(Pn⊠Pn)=2 if n is even. Figure 9 illustrates that C2P8⊠P8=2. From Case 1 and Case 2 we conclude the requested.

Figures

Figure 1

A1={a,b,c},B1={x,y} are 2-unconvertible on Js, m

Figure 2

C2( J6,4)≤11

Figure 3

C2(J6,4)>10

Figure 4

A 2-conversion process on J7,4 starting with |S0|=13

Figure 5

X1,X2,X3 and X4 are 4-unconvertible on P2⊠P6

Figure 6

C4(P2⊠P9)≤10

Figure 7

C4(P2⊠P10)≤12

Figure 8

C2(P9⊠P9)=2

Figure 9