•  
  •  
 

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 ��=0,a set ��0⊆��.is selected and for ��∈{1,2,...,};����is obtained by adding all vertices that have k or more neighbors in ����−1to ����−1. ��0is 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 ��0and for some ��≥0; ����=��(��). 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����is determined for ��≥2.

Keywords

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

Article Type

Article

Download

Share

COinS