# Irreversiblek-Threshold Conversion Number of Circulant Graphs

Authors: Ramy Shaheen; Suhail Mahfud; Ali Kassem
Journal: Journal of Applied Mathematics
 (2022)

---

## Abstract

An irreversible conversion process is a dynamic process on a graph where a one-way change of state (from state 0 to state 1) is applied on the vertices if they satisfy a conversion rule that is determined at the beginning of the study. The irreversiblek-threshold conversion process on a graph G=V,E is an iterative process which begins by choosing a set S0⊆V, and for each step tt=1,2,⋯,,St is obtained from St−1 by adjoining all vertices that have at least k neighbors in St−1. S0 is called the seed set of the k-threshold conversion process, and if St=VG 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 (CkG) is the minimum cardinality of all the IkCSs of G. In this paper, we determine C2G for the circulant graph Cn1,r when r is arbitrary; we also find C3Cn1,r when r=2,3. We also introduce an upper bound for C3Cn1,4. Finally, we suggest an upper bound for C3Cn1,r if n≥2r+1 and n≡0mod2r+1.


---

## Body

## 1. Introduction

As usual,n=V and m=E denote the numbers of vertices and edges at a graph GV,E, respectively. Let degv be the degree of a vertex v; a graph is t-regular if all of its vertices are of degree t. The open neighborhood of a vertex v is Nv=u∈V:uv∈E while the closed neighborhood of v is Nv=Nv∪v. For any undefined term in the paper, we refer to Harary [1]. An irreversible k-threshold conversion process on a graph G=V,E is the process of finding the least number of vertices we need to initially convert in step t=0 in order to spread the conversion to all the remaining vertices of the graph according to a conversion rule. This iterative process starts by choosing a seed set S0⊆V, and for each step tt=1,2,⋯,,St is obtained from St−1 by adjoining all vertices that have at least k neighbors in St−1. S0 is called the seed set of the k-threshold conversion process, and if St=VG 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 (CkG) is the minimum cardinality of all the IkCSs of G. Therefore, 1≤k≤∆G and C1G=1 for connected graphs. The first graph model of the irreversible k-threshold conversion problem was presented by Dreyer and Roberts in [2] where they determined the value of C2 for paths and cycles. For further information on the irreversible k-threshold conversion problem on graphs, see [2–6]. The circulant graph CnS with the connection set S⊆1,2,⋯,n is an undirected graph with the vertex set V=v1,v2,⋯,vn where two vertices vi,vj are adjacent if i−j∈S. Therefore, the circulant graph Cn1 is a cycle, and the circulant graph Cn1,2,⋯,n/2 forms the complete graph Kn. It is obvious that the circulant graph Cn1,r is 4-regular when 1<r≤n−1/2. Through this paper, we will denote the vertex set by V=vii=1,⋯,n taking into consideration that we exchange the subscript of the vertex v0 by vn. For further information on the circulant graph, see [7].Proposition 1 (see [2]).
(1)C2Pn=n+12.Proposition 2 (see [2]).
(2)C2Cn=n2.Proposition 3 (see [2]).
IfG is a k-regular graph, then S is a k-conversion set of G if and only if V−S is independent.Note 1: 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 paper, we determineC2G for the circulant graph Cn1,r for arbitrary r; we also find C3Cn1,r when r=2,3. We also introduce an upper bound for C3Cn1,4. Then we suggest an upper bound for C3Cn1,r if n≥2r+1 and n≡0mod2r+1. Let Cn1,r be a circulant graph on which an irreversible k-threshold conversion process is being studied. Since Cn1,r is 4-regular, we define the k-unconvertable set of G (denoted by U) as follows:
(3)U⊆V−S0andforeveryx∈UthenNx∩U≥4−k+1.which means each vertex of U is unconverted and is adjacent to at least 4−k+1 vertices of U at t=0; therefore, the conversion cannot reach any vertex of U during any step of the process unless at least one of its vertices is converted at t=0. Figure 1 shows a 3-unconvertable set on Cn1,2.Figure 1
X=vi,vi+1,vi+2 is 3-unconvertable on Cn1,2. C121,5. C121,5.J2,m.Note 2: let Cn1,r be a circulant graph, and let the conversion threshold be k=2. We will define a conversion generating path (CGP) as a series of r consecutive vertices (a path) on Cn1,r such as (vi,vi+1,⋯,vi+r−1), so that when all of these vertices are converted in a step t=l, they can spread the conversion to the entire graph by converting two new (unconverted) vertices at every following step. The process goes as follows:t=l: the conversion reaches all vertices of the CGP which are vi,vi+1,⋯,vi+r−1t=l+1: since vi,vi+r−1 are adjacent to both vi−1,vi+r, then conversion spreads to vi−1,vi+r, and the converted vertices are vi−1,vi+1,⋯,vi+r−1,vi+rt=l+2: since vi−1,vi+r are adjacent to both vi−2,vi+r+1, then conversion spreads to vi−2,vi+r+1The conversion process continues until all vertices ofV are converted. This goal is achieved on step t=l+n−r−m/2 where m represents the number of converted vertices of V−VCGP at t=l.Ifn−r−m is even, then the last two unconverted vertices are converted at the last step, which is t=l+n−r−m/2.Ifn−r−m is odd, then at the next to last step t=l+n−r−m/2−1; two unconverted vertices are converted, and then only one unconverted vertex remains to be converted in the last step which is t=l+n−r−m/2. Figure 2 illustrates a 5-vertex CGP on C121,5.
(4)C2Cn1,r.Figure 2
v1,v2,v3,v4,v5 form a CGP on C121,5.In this subsection, we determineC2Cn1,r for arbitrary r when 1<r≤n−1/2.Theorem 4.
Forn≥5,C2Cn1,2=2.Proof.
We know by definition that for any graphG,CkG≥k, which means that C2Cn1,2≥2. Let S0=v1,v2 be the seed set of the conversion process. S0 forms a CGP on Cn1,2 with l=0, and the process goes as follows:
t=0: we convert v1,v2
t=1: the conversion spreads to v3,vn
t=2: the conversion spreads to v4,vn−1The process continues, spreading the conversion to two new (unconverted) vertices each step. Ifn is even, the process ends in step t=n/2−1 when the last two unconverted vertices (vn/2+1,vn/2+2) are converted.Ifn is odd, at the next to last step t=n−2/2−1=n−3/2, there are three unconverted vertices left which are (vn/2,vn/2+1,vn/2+2). Two of them (vn/2,vn/2+2) are converted in t=n−3/2 while the last unconverted vertex (vn/2+1) is converted in the last step t=n−2/2=n−1/2.We conclude thatS0 is an I2CS of Cn1,2 which means C2Cn1,2≤2; therefore,C2Cn1,2=2, and we prove the requested.Theorem 5.
Forn≥7,C2Cn1,3=2.Proof.
SinceC2Cn1,3≥2, we need to prove that C2Cn1,3≤2. Let S0=v1,v3 be the seed set. The process goes as follows:
t=0: we convert S0=v1,v3
t=1: since v2adjv1,v3 the conversion spreads to v2. Similarly, v4adjv1,v3, and we also have vnadjv1,v3 which means S1=v1,v2,v3,v4,vn. Each of the sets v1,v2,v3, v2,v3,v4, and v1,v2,vn forms a CGP on Cn1,3 with l=1.
t=2: the conversion spreads to v5,vn−1
t=3: the conversion spreads to v6,vn−2The process continues similarly to Theorem4 until the graph is successfully converted at step t=n−5/2+1 if n is odd, or at step t=n−5/2+1 if n is even.We conclude thatS0=v1,v3 is an I2CS of Cn1,3 which means C2Cn1,3≤2; then C2Cn1,3=2, and the requested is proven.Theorem 6.
C2Cn1,4=2for9≤n≤11;3otherwise.Proof.
We consider the following cases:Case 1.n=9.
LetS0=v1,v6 be the seed set. The process goes as follows:
t=0: we convert S0=v1,v6
t=1: since v2adjv1,v6 the conversion spreads to v2. Similarly, v5adjv1,v6, and we also have S1=v1,v2,v5,v6
t=2: the conversion spreads to v7,v9; therefore, S2=v1,v2,v5,v6,v7,v9
t=3: the conversion spreads to v3,v4,v8; therefore, S3=VC91,4
We conclude thatC2C91,4=2.Case 2.n=10.
LetS0=v1,v6 be the seed set. The process goes as follows:
t=0: we convert S0=v1,v6
t=1: the conversion spreads to v2.v5,v7,v10 which means S1=v1,v2,v5,v6,v7,v10
t=2: the conversion spreads to v3.v4,v8,v9 which means S2=VC101,4
We conclude thatC2C101,4=2.Case 3.n=11.
LetS0=v1,v6 be the seed set. The process goes as follows:
t=0: we convert S0=v1,v6
t=1: the conversion spreads to v2,v5; therefore, S1=v1,v2,v5,v6
t=2: the conversion spreads to v9 which means S2=v1,v2,v5,v6,v9
t=3: the conversion spreads to v8,v10; therefore, S3=v1,v2,v5,v6,v8,v9,v10
t=4: the conversion spreads to v3.v4,v7,v11 which means S4=VC111,4
We conclude thatC2C111,4=2.Case 4.
n≥12. We start by proving that C2Cn1,4>2 for n≥12. We consider the following subcases:
Case 4.a.S0=v1,v2; since Nv1∩Nv2=∅, then S1=S0, and the conversion does not spread after the initial step t=0, which means the process fails. Without loss of generality, the same argument can be applied for any S0=vi,vi+1:1≤i≤n.
Case 4.b.S0=v1,v3; since Nv1∩Nv3=v2, then at step t=1, we get S1=v1,v2,v3. However, Nv1∩Nv2∩Nv3=∅ which means S2=S1 and the spread stops at the end of step t=1. Without loss of generality, this applies to any S0=vi,vi+2:1≤i≤n.
Case 4.c.S0=v1,v4. In a similar way to the previous two cases, S1=v1,v4,v5,vn, S2=S1 which means the spread stops at the end of step t=1, and without loss of generality; this applies to any S0=vi,vi+3:1≤i≤n.
Case 4.d.S0=v1,v5; then S1=S0, and the process fails at the end of step t=0. Without loss of generality, this applies to any S0=vi,vi+4:1≤i≤n.
Case 4.e.S0=v1,v6; then S1=v1,v2,v5,v6, but S2=S1 and the spread stops at the end of step t=1. Without loss of generality, this applies to any S0=vi,vi+5:1≤i≤n.
Case 4.f.S0=v1,vl:l≥7. Since Nv1∩Nvl=∅, then S1=S0, and the conversion does not spread after the initial step t=0, which means the process fails. Without loss of generality, the same argument can be applied for any S0=vi,vi+l:1≤i≤nandl≥7.
From subcases 4.a to 4.f, we conclude that(5)C2Cn1,4>2.
Now, letS0=v1,v3,v4 be the seed set; then at t=1, the conversion spreads to v2,v5,vn which makes S1=v1,v2,v3,v4,v5,vn. We notice that each set of four consecutive vertices of S1 forms a CGP on Cn1,4 with l=1 and m=2. The process goes as follows:
t=0: we convert S0=v1,v3,v4
t=l=1: S1=v1,v2,v3,v4,v5,vn
t=2:S2=v1,v2,v3,v4,v5,v6,vn−1,vn
The process continues converting two new vertices each step until it ends att=n−4/2 if n is even, or at t=n−3/2 if n is odd. We conclude that S0=v1,v3,v4 is an I2CS of Cn1,4. Therefore
(6)C2Cn1,4≤3.
From (5) and (6), we conclude that C2Cn1,4=3 for n≥12.
From Cases1–4, we conclude the requested.Theorem 7.
Forr≥4,C2Cn1,r=r+1/2.Proof.
Since a CGP is a path of lengthr, and by Proposition 1, C2Pn=n+1/2; therefore, Y=v1,v3,⋯,vm:m=rifrisodd,m=r+1ifriseven can be an I(r+1/2)CS of Cn1,r. This means
(7)C2Cn1,r≤r+12.
Figure3 illustrates an I2CS of 5 vertices on C241,8.Figure 3
An I2CS of 5 vertices onC241,8.We now consider the following cases forr:Case 1.r is odd.
LetS0=v1,v3,⋯,vr−2 be a conversion seed set of cardinality r+1/2−1=r−1/2. The process goes as follows:
t=0: we convert S0=v1,v3,⋯,vr−4,vr−2
t=1: S1=v1,v2,v3,v4⋯,vr−3,vr−2
t=2: S2=v1,v2,v3,v4⋯,vr−3,vr−2=S1. The process stops at the end of step t=1. Without loss of generality, the process applies to all configurations of S0 on the vertices of v1,v2,v3,v4⋯,vr−1,vr. Therefore, S0 cannot produce a CGP on Cn1,r, and since we need to convert at least r+1/2=r+1/2 vertices of the path v1,v2,v3,v4⋯,vr−1,vr in order to convert it entirely, it is impossible to convert Cn1,r if we initially convert less than r+1/2 vertices at t=0, which means C2Cn1,r>r+1/2−1.Case 2.r is even.
LetS0=v1,v3,⋯,vr−1 be a conversion seed set of cardinality r+1/2−1=r/2. The process goes as follows:
t=0: we convert S0=v1,v3,⋯,vr−3,vr−1
t=1: S1=v1,v2,v3,v4⋯,vr−2,vr−1
t=2: S2=v1,v2,v3,v4⋯,vr−2,vr−1=S1
The process stops at the end of stept=1. Without loss of generality, the process applies to all configurations of S0 on the vertices of v1,v2,v3,v4⋯,vr−1,vr. Therefore, S0 cannot produce a CGP on Cn1,r, and since we need to convert at least r+1/2=r+1/2 vertices of the path v1,v2,v3,v4⋯,vr−1,vr in order to convert it entirely, it is impossible to convert Cn1,r if we initially convert less than r+1/2 vertices at t=0, which means C2Cn1,r>r+1/2−1.
From Case1 and Case 2, we conclude that
(8)C2Cn1,r>r+12−1.
From (7) and (8), we conclude that C2Cn1,r=r+1/2.
(9)C3Cn1,r.
In this subsection, we determineC3Cn1,r for r=2,3. Then, we introduce an upper bound for C3Cn1,4. Finally, we introduce an upper bound for C3Cn1,r if n≥2r+1 and n≡0mod2r+1.Theorem 8.
Forn≥5,C3Cn1,2=n/3+1ifn≡0,1mod3,n/3+1ifn≡2mod3.Proof.
We haveC3Cn1,2≥3, and we consider the following cases:Case 1.
n≡0mod3.
LetS0=v3l:1≤l≤n/3∪v1 be the seed set of the conversion process. It is obvious that S0 is of cardinality n/3+1. The process goes as follows:
t=0: we convert S0=v3l:1≤l≤n/3∪v1
t=1: we notice that Nv2∩S0=Nvn−1∩S0=3 which means that the conversion spreads to v2,vn−1 making S1=v3l:1≤l≤n/3∪v1,v2,vn−1
t=2: we notice that Nv4∩S1=Nvn−2∩S1=3; therefore, the conversion spreads to v4,vn−2,whichmakesS2=v3l:1≤l≤n/3∪v1,v2,v4,vn−2,vn−1The process goes on, and with each step, two new (unconverted) verticesvm,vn−d are converted, where 5≤m≤n/2 and m≢0(mod 3). Similarly, 4≤d≤n/2 and m≢0(mod 3). Which means, the next to last step is t=n/3−1, and Sn/3−1 is defined as:
(10)t=n3−1:Sn/3−1=V−vn/2+1ifniseven;V−vn2ifnisodd.t=n/3: the conversion spreads to the last remaining vertex vn/2+1 (or vn/2) if n is odd (or even), respectively, and then the conversion is spread to all vertices of Cn1,2 which makes S0 an I3CS of Cn1,2. Therefore
(11)C3Cn1,2≤n3+1ifn≡0mod3.Letvi,vi+1,vi+2 be three consecutive unconverted vertices of Cn1,2. At any step of the process, in order to convert any of these three vertices, it needs to be adjacent to three converted vertices. However, this is impossible since each one of them is adjacent to the other two and they are all unconverted, which means X=vi,vi+1,vi+2 is 3-unconvertable if X∩S0=∅. We imply that any seed set of cardinality n/3 on Cn1,2 should be distributed as one of the following:
(12)D0=v3l:1≤l≤n3,B0=v3l+1:0≤l≤n3−1,E0=v3l+2:0≤l≤n3−1.Let us assume thatD0 is the seed set. The conversion process goes as follows:t=0: we convert D0=v3l:1≤l≤n/3t=1: with the absence of any unconverted vertex that is adjacent to three vertices of D0, then D1=D0 which means the spread stops at the end of step t=0. Therefore, the process fails. Without loss of generality, the same result can be obtained if the seed set was B0 or E0, then:
(13)C3Cn1,2>n/3ifn≡0mod3From (11) and (13), we conclude that C3Cn1,2=n/3+1 if n≡0mod3.Case 2.
n≡1mod3.
Similarly to Case1, a seed set of cardinality n/3 is not enough to convert Cn1,2. Let the seed set be S0=v3l:1≤l≤n−1/3∪vn. It is obvious that S0=n−1/3+1=n/3+1. The process goes (similarly to Case 1) as follows:
t=0: we convert S0=v3l:1≤l≤n−1/3∪vn
t=1: since Nv1∩S0=Nvn−2∩S0=3, the conversion spreads to v2,vn−2,whichmakesS1=v3l:1≤l≤n−1/3∪v1,vn−2,vn
t=2: since Nv2∩S1=Nvn−3∩S1=3, the conversion spreads to v2,vn−3,whichmakesS2=v3l:1≤l≤n−1/3∪v1,v2,vn−3,vn−2,vnThe process goes on, and with each step, two new (unconverted) verticesvm,vn−d are converted, where 4≤m≤n/2 and m≢0(mod 3). Similarly, 5≤d≤n/2 and m≢0(mod 3), which means the next to last step is t=n/3−1, and Sn/3−1 is defined as:
(14)t=n3−1:Sn3−1=V−vn2−1,vn2+1ifnisodd;V−vn/2−1,vn/2ifniseven.t=n/3: the conversion spreads to the last two unconverted vertices vn/2,vn/2+1 if nisodd, or vn/2−1,vn/2 if niseven. Either way, the process ends successfully at the end of t=n/3 which means S0 is an I3CS of Cn1,2 and C3Cn1,2≤n/3+1. However, since C3Cn1,2>n/3, we conclude that C3Cn1,2=n/3+1 if n≡1mod3.Case 3.
n≡2mod3.
Similarly to Case1 and Case 2, C3Cn1,2>n/3 and in order to avoid getting any version of X on Cn1,2, the seed set must take one of the following forms:
(15)D0=v3l:1≤l≤n/3∪x:x∈v1,vn,B0=v3l+1:0≤l≤n3−1∪x:x∈vn−2,vn−1,E0=v3l+2:0≤l≤n3−1∪x:x∈vn−1,vn.
LetD0 be the seed set (of cardinality n/3+1=n/3). The process goes as follows:
t=0: we convert D0=v3l:1≤l≤n/3∪x:x∈v1,vn. Whether x=v1 or x=vn, the conversion does not spread to any vertex from V−D0 because no vertex of V−D0 is adjacent to three vertices of D0
t=1: D1=D0, and the process fails. Without loss of generality, the same result is obtained if the seed set was B0 or E0; therefore
(16)C3Cn1,2>n3+1ifn≡2mod3.
LetS0=v3l:1≤l≤n/3∪vn−1,vn be seed set of cardinality n/3+1=n/3+1. The process goes as follows:
t=0: we convert S0=v3l:1≤l≤n/3∪vn−1,vn
t=1: the conversion spreads to v1,vn−3
t=2: the conversion spreads to v2,vn−4
Similarly to Case1 and Case 2, by the end of each step, two new (unconverted) vertices are converted, and the process continues until the last step t=n/3 when the last two unconverted vertices which are vn/2,vn/2−2 (in case n is even), and vn/2,vn/2−1 (in case n is odd) get converted and then the conversion process reaches the entire graph. We conclude that:
(17)C3Cn1,2≤n3+1ifn≡2mod3.
From (16) and (17), we conclude that C3Cn1,2=n/3+1ifn≡2mod3.
From all the previous cases, we conclude the requested.Proposition 9.
A set ofr+1 consecutive unconverted vertices in Cn1,r is 3-unconvertable.Proof.
Let there be a conversion process onCn1,r, and at the initial step t=0, let the set X=vi,vi+1,vi+r−1,vi+r be a set of r+1 unconverted vertices. Every vertex of X is of degree 4 and is adjacent to two other vertices of X. Since k=3, it is impossible for any of these vertices to satisfy the conversion condition at any step of the conversion process even if all the vertices of V−X get converted, which means X is 3-unconvertble.Theorem 10.
Forn≥7 we have:
(18)C3Cn1,3=3n/8;n≡0mod8,/n/4+n/8+1;n≡0,1,2mod4andn≢0,1,2mod8;./3n/8+1;n≡1,2,3mod8,/n/4+n/8+2;n≡3mod4andn≢3mod8.Proof.
LetS0 be the seed set of the conversion process. We implied in Proposition 9 that the process fails if V−S0 contains four (or more) consecutive vertices, which means S0 contains at least n/4 vertices. Let D0,E0,L0,B0 be the following sets:
(19)D0=v4l:1≤l≤n4,E0=v4l+1:0≤l≤n4−1,L0=v4l+2:0≤l≤n4−1,B0=v4l+3:0≤l≤n4−1.In order to avoid having four consecutive unconverted vertices,S0 must contain either D0,E0,L0,orB0. We assume that D0⊆S0; we notice that the vertices of D0 divide Cn1,3 into n/4 subgraph, each of which consists of four consecutive vertices, and only one of these vertices is converted at t=0. We denote these subgraphs by SGi:1≤i≤n/4, when:
(20)SG1=v1,v2,v3,v4,SG2=v5,v6,v7,v8,⋮SGn2=vn−m−3,vn−m−2,vn−m−1,vn−m.We take into consideration thatm∈0,1,2,3 if n≡0,1,2,3mod4, respectively. The last m vertices form a minisubgraph of 1,2, and 3 vertices if n≡1,2,3mod4, respectively. We imply that for S0=D0, the conversion does not spread to any vertex of V−S0 because none of them is adjacent to three vertices of S0 which means S1=S0=D0, and the process fails. This means D0⊂S0. Let Y=vi,vi+1,vi+2,vi+3,vi+4 be a set of five consecutive vertices where the middle vertex vi+2 is the only converted vertex of Y; then the four unconverted vertices of Y form a 3-unconvertable set on Cn1,3 and that is because each of them is adjacent to two other unconverted vertices of Y, which means there cannot be a step t when any of these four vertices satisfies the conversion rule (being adjacent to three or more converted vertices). We conclude that there cannot be two consecutive subgraphs SGi,SGi+1, of the subgraphs identified previously, or else, a version of Y will be created consisting of the last two vertices of SGi and the first three vertices of SGi+1; this means that we need to add at least one converted vertex to one of every two consecutive subgraphs. Therefore
(21)C3Cn1,3≥3n8ifn≡0,1,2,3mod8;n4+n8+1ifn≡0,1,2,3mod4andn≢0,1,2,3mod8.We consider the following cases forn:Case 1.n≡0mod4.
We consider two subcases:
Case 1.a.n≡0mod8.
In this subcase, we have an even number of subgraphs onCn1,3 and m=0. Let M0 be the following set: M0=v2+8l:0≤l≤n/8−1. Let S0=D0∪M0 be the seed set. It is obvious that S0=3n/8. The conversion process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1
t=1: the conversion spreads to v1+8l,v3+8l,v5+8l,v7+8l:0≤l≤n−8−1
t=2: the conversion spreads to v6+8l:0≤l≤n/8−1
By the end of stept=2, the conversion reaches all vertices of Cn1,3; therefore, S0 is an I3CS of Cn1,3 and C3Cn1,3≤3n/8, and from (21), we conclude that C3Cn1,3=3n/8 when n≡0mod8.
Case 1.b.n≡0mod4 and n≢0mod8.
This subcase is similar to subcase 1.a with the only difference of having an odd number of subgraphs. This means we need to convert one additional vertexvn−2. The conversion process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪vn−2
t=1: the conversion spreads to v1+8l,v3+8l,v5+8l,v7+8l:0≤l≤n/8−1vn−1
t=2: the conversion spreads to the remaining vertices which are v6+8l:0≤l≤n/8−1
Therefore,S0 is an I3CS of Cn1,3 and since S0=n/4+n/8+1, according to (21), we conclude that C3Cn1,3=n/4+n/8+1 if n≡0mod4 and n≢0mod8. Figure 4 illustrates an I3CS of 8 vertices on C201,3.Case 2.n≡1mod4.
We consider two subcases:
Case 2.a.n≡1mod8.
In this subcase, we have an even number of subgraphs onCn1,3 and m=1. Let D0 and M0 be the same sets identified in subcase 1.a. Let the seed set be N0=D0∪M0. In a similar process to the one in subcase 1.a, all vertices of V−vn−3,vn−2,vn−1,vn,v1 by the end of step t=2. However, the five consecutive vertices vn−3,vn−2,vn−1,vn,v1 form a version of Y which was identified in Theorem 8 as containing a 3-unconvertable set. In addition to that, since taking out any vertex from D0∪M0 results in a version of either XorY on Cn1,3, we conclude that C3Cn1,3>3n/8 in this subcase. Let S0=D0∪M0∪v1 be the seed set of cardinality 3n/8+1; the process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪v1
t=1: the conversion spreads to v1+8l,v3+8l:1≤l≤n/8−1∪v5+8l,v7+8l:0≤l≤n/8−1∪vn−2
t=2: the conversion spreads to v6+8l:0≤l≤n/8−1 which means vn−3 is converted at this step as well
t=3: the conversion spreads to v3,vn
By the end of stept=3, the conversion reaches all vertices of Cn1,3; therefore, S0 is an I3CS of Cn1,3, and since S0=3n/8+1, we conclude that C3Cn1,3=3n/8+1 if n≡1mod8.
Case 2.b.n≡1mod4 and n≢1mod8.
This subcase is similar to subcase 2.a with the only difference of having an odd number of SGs. This means that similarly to subcase 1.b, we need to convert one additional vertex from this last subgraphvn−3; the process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪v1
t=1: the conversion spreads to v1+8l,v3+8l:1≤l≤n/8−1∪v5+8l,v7+8l:0≤l≤n/8−1∪vn−2
t=2: the conversion spreads to v6+8l:0≤l≤n/8−1
t=3: the conversion spreads to v3,vn−4
t=4: the conversion spreads to vn−3,vn
By the end of stept=4, the conversion reaches all vertices of Cn1,3. Therefore, S0 is an I3CS of Cn1,3, and since S0=n/4+n/8+1, this means C3Cn1,3=n/4+n/8+1 if n≡1mod4 and n≢1mod8.Case 3.n≡2mod4.
We consider two subcases:
Case 3.a.n≡2mod8.
In this subcase, we have an even number of subgraphs onCn1,3 and m=2. Let D0 and M0 be the same sets identified in subcase 1.a. Let the seed set be N0=D0∪M0. In a similar process to the one in subcase 1.a, all vertices of V−vn−4,vn−3,vn−1,vn,v1 by the end of step t=2. However, the five consecutive vertices vn−4,vn−3,vn−2,vn−1,vn form a version of Y, and since taking out any vertex from D0∪M0 results in a version of either XorY, we conclude that C3Cn1,3>3n/8 in this subcase as well. Let S0=D0∪M0∪vn be the seed set of cardinality 3n/8+1; the process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪vn
t=1: the conversion spreads to v1+8l,v3+8l,v5+8l,v7+8l:0≤l≤n/8−1∪vn−1 which means v1,vn−3,vn−1 are converted in this step
t=2: the conversion spreads to v6+8l:0≤l≤n/8−1 which means vn−4 is converted at this step
By the end of stept=2, the conversion reaches all vertices of Cn1,3; therefore, S0 is an I3CS of Cn1,3, and since S0=3n/8+1, we conclude that C3Cn1,3=3n/8+1 if n≡2mod8.
Case 3.b.n≡2mod4 and n≢2mod8.
By following the same argument in subcase 1.b and subcase 3.a, letS0=D0∪M0∪vn−4 be the seed set of cardinality n/4+n/8+1; the process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪vn−4
t=1: the conversion spreads to the vertices v1+8l,v5+8l,v7+8l:0≤l≤n/8−1∪v3+8l:1≤l≤n/8−1∪vn−5,vn−3,vn−1 which means v1,vn−5,vn−3,vn−1 are converted in this step
t=2: the conversion spreads to the vertices v6+8l:0≤l≤n/8−1∪vn
t=3: the conversion spreads to the last unconverted vertex v3, and the entire graph is converted
We conclude thatC3Cn1,3=n/4+n/8+1 if n≡2mod4 and n≢2mod8.Case 4.
n≡3mod4.
We consider two subcases:
Case 4.a.n≡3mod8.
In this subcase, we have an even number of subgraphs onCn1,3 and m=3. Let D0 and M0 be the same sets identified in subcase 1.a. Let the seed set be N0=D0∪M0. In a similar process to the one in subcase 1.a, all vertices of V−v1,v3,vn−5,vn−4,vn−2,vn−1,vn by the end of step t=2. However, the five consecutive vertices vn−5,vn−4,vn−3,vn−2,vn−1 form a version of Y, and since taking out any vertex from D0∪M0 results in a version of either XorY, we conclude that C3Cn1,3>3n/8 in this subcase as well. Let S0=D0∪M0∪vn−1 be the seed set of cardinality 3n/8+1; the process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪vn−1
t=1: vertices v5+8l,v7+8l:0≤l≤n/8−1∪v1+8l,v3+8l:1≤l≤n/8 are converted, which means vn−4 is converted at this step
t=2: the conversion spreads to v6+8l:0≤l≤n/8−1 which means vn−5 is converted at this step
t=3: v3,vn−2 are converted
t=4: v1,vn are converted
By the end of stept=4, the conversion reaches all vertices of Cn1,3; therefore, S0 is an I3CS of Cn1,3, and since S0=3n/8+1, we conclude that C3Cn1,3=3n/8+1 if n≡3mod8.
Case 4.b.n≡3mod4 and n≢3mod8. We consider two subcases:
Case 4.b.1.n=7.
This proof is equivalent to proving thatC3C71,3=3. It is obvious by definition that C3C71,3≥3. Let S0 be a seed set of cardinality 3 and defined as S0=v1,v3,v6. The process goes as:
(22)t=0:S0=v1,v3,v6.t=1:S1=S0∪v2,v7.t=2:S2=S1∪v4,v5=VC71,3which means C3C71,3≤3; therefore, C3C71,3=3.
Case 4.b.2.n≥11.
LetS0=D0∪M0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1; then that would make the following nine vertices vn−9,vn−8,vn−6,vn−5,vn−4,vn−2,vn−1,vn,v1 unconverted which means creating several versions of A1, and the process fails. Now let S0=D0∪M0∪vx be the seed set. We consider the following options for vx:(i)
Ifvx∈vn−9,vn−8,vn−6,vn−5, then vn−2,vn−1,vn,v1 are four consecutive unconverted vertices; therefore, they form a version of A1, and the process fails. However, we notice that(ii)
Ifvx∈vn−4,vn−2,vn−1,vn,v1, then (vn−9,vn−8,vn−7,vn−6,vn−5) form a version of Y, and since Y is 3-unconvertable, then the process fails(iii)
Ifvx∉vn−9,vn−8,vn−6,vn−5,vn−4,vn−2,vn−1,vn,v1, then vn−2,vn−1,vn,v1 form a version of A1, (vn−9,vn−8,vn−7,vn−6,vn−5) form a version of Y, and the process fails
We concludeD0∪M0∪vx cannot be a I3CS of Cn1,3 when n≡3mod4 and n≢3mod8 which means that C3Cn1,3>n/4+n/8+1 if n≡2mod4 and n≢2mod8.
Now letS0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪vn−5,vn−1 be the seed set of cardinality n/4+n/8+2; the process goes as follows:
t=0: we convert S0=v4l:1≤l≤n/4∪v2+8l:0≤l≤n/8−1∪vn−5,vn−1
t=1: the conversion spreads to v1+8l,v3+8l:1≤l≤n/8−1∪v5+8l,v7+8l:0≤l≤n/8−1∪vn−6,vn−4,vn−2
t=2: the conversion spreads to v6+8l:0≤l≤n/8−1∪v1
t=3: the last two unconverted vertices v3,vn get converted which means the entire graph is converted at the end of this step
We conclude thatS0 is an I3CS, and therefore, C3Cn1,3=n/4+n/8+2 if n≡3mod4 and n≢3mod8.
From all cases and subcases, we conclude the requested.Theorem 11.
Forn≥9.(23)C3Cn1,4≤2n5+2ifn∈9,14,19;2n5ifn≡0,5,6,7mod10andn∉16,17;2n5+1otherwise.Proof.
We implied in Proposition9 that the conversion process fails if there are five consecutive unconverted vertices on Cn1,4 at t=0, which means the conversion seed set S0 cannot consist of less than n/5 vertices. Let D0=v5l:1≤l≤n/5; we assume that D0⊆S0, and we notice that the vertices of D0 divide the first 5n/5 vertices of VCn1,4 into n/5 subgraphs, each of which consists of four consecutive unconverted vertices followed by one converted vertex. We denote them by SGi:1≤i≤n/5. The two adjacent subgraphs SG3,SG4 together have two converted vertices {v15,v20} and eight unconverted vertices which are v11,v12,v13,v14,v16,v17,v18,v19. We notice that the set U=v12,v13,v16,v17 consists of four unconverted vertices each of which is adjacent to two vertices of U which means U is 3-unconvertable. Therefore, the process fails if S0=D0, Without loss of generality, the same argument applies to any SGi,SGi+1:1≤i≤n/5−1. Let us now try to find a configuration of converted vertices that prevents having any unconvertable sets and at the same time guarantees total conversion of SG3,SG4. We imply that converting v13,v15,v17,v20 and applying this configuration to the neighboring subgraphs SG1,SG2,SG5,SG6 achieves the requested for SG3,SG4 as shown in Figure 5.Figure 4
An I3CS of 8 vertices onC201,3.Figure 5
A configuration to convertSG3,SG4 starting with 8 converted vertices at t=0.Therefore, we apply this configuration to every two adjacent subgraphs. As for the remainingn−10n/10, we will need to convert additional vertices in order to convert them. In that regard, we consider the following cases of n:Case 1.
n≡0mod10.
LetS0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n/10−1 be the seed set. The process goes as follows:
t=0: we convertS0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n/10−1
t=1: the conversion spreads to v1+10l,v4+10l,v6+10l,v9+10l:0≤l≤n/10−1
t=2: the remaining unconverted vertices which are v2+10l,v8+10l:0≤l≤n/8−1 get convertedBytheend of step t=2, the entire graph’s vertex set is converted. We conclude that S0 is an I3CS of cardinality 2n/5, which means C3Cn1,4≤2n/5 if n≡0mod10. Figure 6 illustrates that C201,4≤8.Case 2.
n≡1mod10.
LetS0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n/10−1Uv1 be the seed set. The process goes as follows:
(24)t=0:S0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n10−1Uv1,t=1:S1=S0∪v1+10j,v4+10l,v6+10l,v9+10l:1≤j≤n10,0≤l≤n10−1Uvn,t=2:S2=S1∪v2+10l,v8+10d:0≤l≤n10−1,1≤d≤n10−1Uv4,t=3:S3=S2∪v8,vn−2=VCn1,4.
Therefore,S0 is I3CS of Cn1,4 which means C3Cn1,4≤2n/5+1 if n≡1mod10.Case 3.
n≡2mod10.
LetS0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n/10−1Uvn be the seed set. The process goes as follows:
(25)t=0:S0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n10−1Uvn,t=1:S1=S0∪v1+10j,v4+10l,v6+10l,v9+10t:1≤j≤n10,0≤l≤n10−1,0≤t≤n10−2,t=2:S2=S1∪v2+10l,v8+10l:0≤l≤n10−1,t=3:S3=S2∪v1,vn−3=VCn1,4.
Therefore,S0 is I3CS of Cn1,4 which means C3Cn1,4≤2n/5+1 if n≡2mod10.Case 4.
n≡3mod10.
LetS0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n/10−1Uvn be the seed set. The process goes as follows:
(26)t=0:S0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n10−1Uvn,t=1:S1=S0∪v1+10l,v4+10l,v6+10l,v9+10l:0≤l≤n10−1,t=2:S2=S1∪v2+10l,v8+10l:0≤l≤n10−1,t=3:S3=S2∪vn−2,vn−1=VCn1,4.
Therefore,C3Cn1,4≤2n/5+1 if n≡3mod10.Case 5.
n≡4mod10.
We consider the following subcases:
Case 5.a.n=14.
Let the seed set beS0=v1,v4,v7,v9,v11,v13 which is of cardinality 2n/5+2. Then
(27)t=0:S0=v1,v4,v7,v9,v11,v13,t=1:S1=S0∪v3,v5,v8,v14,t=2:S2=S1∪v10,v12,t=3:S3=S2∪v2,v6=VC141,4.
Therefore,C3C141,4≤2n/5+2.
Case 5.b.n≥24 and n≡4mod10.
Let the seed set beS0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n/10−1Uvn−2. The process goes as follows:
(28)t=0:S0=v3+10l,v5+10l,v7+10l,v10+10l:0≤l≤n10−1Uvn−2,t=1:S1=S0∪v1+10j,v4+10d,v6+10l,v9+10t:1≤j≤n10,1≤d≤n10−1,0≤l≤n10−1,0≤t≤n10−2,t=2:S2=S1∪v2+10l,v8+10d:0≤l≤n10−1,1≤d≤n10−1,t=3:S3=S2∪v1,v8,vn−5,t=4:S4=S3∪v4,vn−1,t=5:S5=S4∪vn=VCn1,4.
Therefore,C3Cn1,4≤2n/5+1 if n≥24 and n≡4mod10.Case 6.
n≡5mod10.
LetS0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n/10,0≤l≤n/10−1 be the seed set. The process goes as follows:
(29)t=0:S0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n10,0≤l≤n10−1.t=1:S1=S0∪v1+10j,v4+10p,v6+10l,v9+10l:1≤j≤n10,0≤p≤n10,0≤l≤n10−1.t=2:S2=S1∪v2+10l,v8+10l:0≤l≤n10−1.t=3:S3=S2∪v1,vn−3=VCn1,4,which means C3Cn1,4≤2n/5 if n≡5mod10.Case 7.
n≡6mod10.
We consider the following subcases:
Case 7.a.n=16.
Let the seed set beS0=v3,v5,v7,v10,v13,v15,v16 which is of cardinality 2n/5+1. The process involves the following steps:
(30)t=0:S0=v3,v5,v7,v10,v13,v15,v16,t=1:S1=S0∪=v1,v4,v6,v9,v11,v14,t=2:S2=S1∪v2,v8,v12=VC161,4.
Therefore,C3C161,4≤2n/5+1.
Case 7.b.n≥26 and n≡6mod10.
LetS0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n/10,0≤l≤n/10−1 be the seed set. The process goes as follows:
(31)t=0:S0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n/10,0≤l≤n/10−1,t=1:S1=S0∪v1+10j,v4+10j,v6+10l,v9+10l:1≤j≤n10,0≤l≤n10−1.t=2:S2=S1∪v2+10l,v8+10d:0≤l≤n10−1,1≤d≤n10−1.t=3:S3=S2∪v1,v8,vn−4.t=4:S4=S3∪v4,vn=VCn1,4.
We conclude thatC3Cn1,4≤2n/5 if n≥26 and n≡6mod10.Case 8.n≡7mod10.
We consider the following subcases:
Case 8.a.n=17.
Let the seed set beS0=v3,v5,v7,v10,v13,v15,v16 which is of cardinality 2n/5+1. The process involves the following steps:
(32)t=0:S0=v3,v5,v7,v10,v13,v15,v17,t=1:S1=S0∪=v4,v6,v9,v11,v14,v16,t=2:S2=S1∪v1,v2,v8,v12=VC171,4.
Therefore,C3C171,4≤2n/5+1.
Case 8.b.n≥27 and n≡7mod10.
LetS0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n/10,0≤l≤n/10−1 be the seed set. The process goes as follows:
(33)t=0:S0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n10,0≤l≤n10−1,t=1:S1=S0∪v1+10j,v4+10j,v6+10l,v9+10l:1≤j≤n10,0≤l≤n10−1,t=2:S2=S1∪v2+10l,v8+10d:0≤l≤n10−1,1≤d≤n10−1,t=3:S3=S2∪v1,v8,vn−5,t=4:S4=S3∪v4,vn−1,t=5:S5=S4∪vn=VCn1,4.
Therefore,C3Cn1,4≤2n/5 if n≥27 and n≡7mod10.Case 9.n≡8mod10.
LetS0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n/10,0≤l≤n/10−1Uvn be the seed set. The process goes as follows:
(34)t=0:S0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n10,0≤l≤n10−1Uvn,t=1:S1=S0∪v1+10p,v4+10p,v6+10l,v9+10l:0≤p≤n10,0≤l≤n10−1Uvn−1,t=2:S2=S1∪v2+10l,v8+10l:0≤l≤n10−1,t=3:S3=S2∪vn−6,vn−2=VCn1,4.
Therefore,C3Cn1,4≤2n/5+1 if n≡8mod10. Figure 7 illustrates that C281,4≤11.Case 10.n≡9mod10.
We consider the following subcases:
Case 10.a.n=9.
Let the seed set beS0=v1,v3,v6,v8 which is of cardinality 2n/5+2. The process involves the following steps:
(35)t=0:S0=v1,v3,v6,v8,t=1:S1=S0∪=v2,v7,v9,t=2:S2=S1∪v4,v5=VC91,4.
Therefore,C3C91,4≤2n/5+2.
Case 10.b.n=19.
Let the seed set beS0=v1,v3,v5,v7,v10,v13,v15,v17 which is of cardinality 2n/5+2. The process goes as follows:
(36)t=0:S0=v1,v3,v5,v7,v10,v13,v15,v17,t=1:S1=S0∪v2,v6,v9,v11,v14,v16,t=2:S2=S1∪v12,v18,t=3:S3=S2∪v8,v19,t=4:S4=S3∪v4=VC191,4.
Therefore,C3C191,4≤2n/5+2.
Case 10.c.n≥29 and n≡9mod10.
LetS0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n/10,0≤l≤n/10−1Uv1 be the seed set. The process goes as follows:
(37)t=0:S0=v3+10p,v5+10p,v7+10l,v10+10l:0≤p≤n10,0≤l≤n10−1∪v1,t=1:S1=S0∪v1+10j,v4+10j,v6+10l,v9+10l:1≤j≤n10,0≤l≤n10−1,t=2:S2=S1∪v2+10l,v8+10d:0≤l≤n10−1,1≤d≤n10−1,t=3:S3=S2∪v8,vn−7,t=4:S4=S3∪v4,vn−3,t=5:S5=S4∪vn−2,vn,t=6:S6=S2∪vn−1=VCn1,4.
Therefore,C3Cn1,4≤2n/5+1 if n≥29 and n≡9mod10.Figure 6
C201,4≤8.Figure 7
An I3CS of 11 vertices onC281,4.From all the previous cases and subcases, we conclude the requested.Theorem 12.
Forn≥2r+1 and n≡0mod2r+1:C3Cn1,r≤nr/2r+1.Proof.
Proposition9 implies that the conversion process fails if there are r+1 consecutive unconverted vertices on Cn1,4 at t=0. We divide the vertices of VCn1,r into n/2r+1 subgraphs denoted by SGi:1≤i≤n/2r+1. Now we try to find a configuration of converted vertices of a random subgraph (SGi) at t=0 so that when applied to all the subgraphs, it results in converting all of VCn1,r. We consider the following cases for r:Case 1.
r is even. Let the configuration of converted vertices we apply to SG1 at t=0 be v1+2l,vr+4+2m:0≤l≤r/2,0≤m≤r−4/2. This means we convert r vertices from each subgraph. As shown in Figure 8, in step t=1, the conversion spreads to v2l:0≤l≤r/2,0≤m≤r−2/2. In the following step t=2, the conversion spreads to v2r+2. In step t=3, the conversion spreads to vr+2. In step t=4, the configuration converts SG1 entirely.Figure 8
A configuration to convertSG1 starting with r converted vertices when r is even.Without loss of generality, by applying the same configuration to all subgraphs, we form an I3CS of cardinalitynr2r+1. We denote it by S0, and the process goes as follows:
(38)t=0:S0=v1+2l+i2r+2,vr+4+2m+i2r+2:0≤i≤n2r+1−1,0≤l≤r2,0≤m≤r−42,t=1:S1=S0∪v2l+i2r+2,vr+3+2m+i2r+2:0≤i≤n2r+1−1,2≤l≤r2,0≤m≤r−22,t=2:S2=S1∪vi2r+2:1≤i≤n2r+1,t=3:S3=S2∪vr+2+i2r+2:0≤i≤n2r+1−1,t=4:S4=S3∪v2+i2r+2:0≤i≤n2r+1−1=VCn1,r.Therefore,S0 is an I3CS which means C3Cn1,r≤nr/2r+1ifn≡0mod2r+1 and r is even.Case 2.r is odd.
Let the seed set beS0=v2l+i2r+2:0≤i≤n/2r+1−1,1≤l≤r. The process goes as follows:
(39)t=0:S0=v2l+i2r+2:0≤i≤n2r+1−1,1≤l≤r,t=1:S1=S0∪v1+2l+i2r+2:0≤i≤n2r+1−1,0≤l≤r,t=2:S2=S1∪v2r+2+i2r+2:0≤i≤n2r+1=VCn1,r.
Therefore,S0 is an I3CS which means C3Cn1,r≤nr/2r+1ifn≡0mod2r+1 and r is odd. Figure 9 illustrates how converting S0 at t=0 results in converting SG1 entirely at the end of step t=2, taking into consideration that vn−r+1∈VSGn/2r+1∩S0 and v1+3r∈VSG1∩S0.Figure 9
A configuration to convertSG1 starting with r converted vertices when r is odd.Without loss of generality, the same argument applies to all subgraphs. From Case1 and Case 2, we conclude the requested.



---

*Source: 1250951-2022-08-11.xml*