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

## Authors

• Ali Kassem Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.
• Suhail Mahfud Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria. https://orcid.org/0000-0002-1275-9191
• Ramy Shaheen Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.

## Keywords:

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

## 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 .

## References

Aisyah S, Utoyo MI, Susilowati L. The Fractional Local Metric Dimention of Comb Product Graphs. Baghdad Sci J. 2020; 17(4): 1288-1293. http://dx.doi.org/10.21123/bsj.2020.17.4.1288.

Mao Y, Dankelmann P, Wang Z. Steiner diameter,maximum degree and size of a graph. Discrete Math. 2021; 344(8), 112468. https://doi.org/10.1016/j.disc.2021.112468.

Bickle A. Fundementals in Graph Theory. USA: American Mathematical Society. 2020; 336 p.

Dreyer PA, Roberts FS. Irreversible k-threshold processes: Graph theoretical threshold models of the spread of disease and of opinion. Discret Appl Math. 2009; 157(7): 615-1627. https://doi.org/10.1016/j.dam.2008.09.012 .

Wodlinger JL. Irreversible k-Threshold Conversion Processes on Graphs. PhD thesis. University of Victoria; 2018. .

Mynhardt CM, Wodlinger JL. The k-conversion number of regular graphs. AKCE Int J Graphs Comb. 2020; 17(3): 955-965. https://doi.org/10.1016/j.akcej.2019.12.016 .

Shaheen R, Mahfud S, Kassem A. Irreversible k-Threshold Conversion Number of Circulant Graphs. J Appl Math. 11 August 2022; 2022: 14 pages. https://doi.org/10.1155/2022/1250951.

Uma L, Rajasekaran G. On alpha labeling of tensor product of paths and cycles. Heliyon. 2023, e21430. https://doi.org/10.1016/j.heliyon.2023.e21430

Praveenkumar L, Mahadevan G, Sivagnanam C. An Investigation of Corona Domination Number for Some Special Graphs and Jahangir Graph. Baghdad Sci J. 2023; 20(1(Special issue)) ICAAM: 294-299. https://dx.doi.org/10.21123/bsj.2023.8416