Irreversible k-Threshold Conversion Number of Circulant Graphs

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 irreversible k-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≡0mod 2r+1.