Irreversible k-Threshold Conversion Number of Circulant Graphs. (11th August 2022) - Shaheen, Ramy; Mahfud, Suhail; Kassem, Ali
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 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 if S t = V G for some t ≥ 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 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 ≥ 2 r + 1 and n ≡ 0 mod   2 r + 1 .