Irreversible \(k\)-threshold conversion number of circulant graphs (Q2676193)

Summary: 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 irreversible \(k\)-threshold conversion process on a graph \(G=(V, E)\) is an iterative process which begins by choosing a set \(S_0\subseteq V\), and for each step \(t\) (\(t =1, 2, \cdots,\)), \(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 if \(S_t = V(G)\) for some \(t\geq0\), then \(S_0\) is an irreversible \(k\)-threshold conversion set (IkCS) of \(G\). The \(k\)-threshold conversion number of \(G\) (denoted by (\(C_k(G)\)) is the minimum cardinality of all the IkCSs of \(G\). In this paper, we determine \(C_2(G)\) for the circulant graph \(C_n(\{1, r\})\) when \(r\) is arbitrary; we also find \(C_3(C_n(\{1, r\}))\) when \(r=2, 3\). We also introduce an upper bound for \(C_3(C_n(\{1, 4\}))\). Finally, we suggest an upper bound for \(C_3(C_n(\{1, r\}))\) if \(n\geq2(r + 1)\) and \(n\equiv0\pmod{2(r + 1)}\).