A New Invariant Regarding Irreversible k-Threshold Conversion Processes on Some Graphs

Abstract

An irreversible k-threshold conversion (k-conversion in short) process on a graph is a specific type of graph diffusion problems which particularly studies the spread of a change of state of the vertices of the graph starting with an initial chosen set while the conversion spread occurs according to a pre -determined conversion rule. Irreversible k-conversion study the diffusion of a conversion of state (from 0 to 1) on the vertex set of a graph . At the first step a set .is selected and for is obtained by adding all vertices that have k or more neighbors in to . is called the seed set of the process and a seed set is called an irreversible k-threshold conversion set (IkCS) of if the following condition is achieved: Starting from and for some ; . The minimum cardinality of all the IkCSs of is called the k- conversion number of (denoted as ( ). In this paper, a new invariant called the irreversible k-threshold conversion time (denoted by ( ) is defined. This invariant retrieves the minimum number of steps that the minimum IkCS needs in order to convert entirely. is studied on some simple graphs such as paths, cycles and star graphs. and are also determined for the tensor product of a path and a cycle ( which is denoted by ) for some values of Finally, of the Ladder graph .

Keywords

• Graph conversion process, k-Threshold conversion number, k-Threshold conversion time, Ladder graph, Seed set, Tensor product