A New Invariant Regarding Irreversible k-Threshold Conversion Processes on Some Graphs
DOI:
https://doi.org/10.21123/bsj.2024.9271Keywords:
Graph conversion process, k-Threshold conversion number, k-Threshold conversion time, Ladder graph, Seed set, Tensor productAbstract
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 .
Received 15/06/2023,
Revised 22/01/2023,
Accepted 24/01/2023,
Published Online First 20/03/2024
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
Downloads
Issue
Section
License
Copyright (c) 2024 Ali Kassem, Suhail Mahfud, Ramy Shaheen
This work is licensed under a Creative Commons Attribution 4.0 International License.
How to Cite
