Volume 11 β’ Issue 2 β’ PP: 60-72 β’ 2024
Irreversible k-Threshold Conversion Number of Strong Grids for k>3
View PDF Abstract
An irreversible k-threshold conversion process on a graph πΊ=(π,πΈ) is a dynamic, iterative process which begins by choosing a set π0⊆π. For each step π‘(π‘=1,2,…,), ππ‘ is obtained from ππ‘−1 by adjoining all vertices that have at least k neighbors in ππ‘−1. We call π0 the seed set of the k-threshold conversion process and if ππ‘=π(πΊ) for some π‘≥0, then π0 is called an irreversible k-threshold conversion set (IkCS) of πΊ. The k-threshold conversion number of πΊ (denoted by (πΆπ(πΊ)) is the minimum cardinality of all the IkCSs of πΊ. In this paper, we study Irreversible k-threshold conversion processes on strong grids ππβ ππ. We determine πΆπ(π3β ππ) for π=5,6,7 and πΆπ(π4β ππ) for π=6,7. We also present upper bounds for πΆ4(π3β ππ), πΆ4(π4β ππ),πΆ5(π3β ππ), then we determine πΆ8(ππβ ππ) for arbitrary π,π.
Keywords
References
[1] Adams SS, Brass Z, Stokes C, Troxell DS. Irreversible k-threshold and majority conversion processes on complete multipartite graphs and graph products. Australas J Comb. 2015; 61: 156-174. Available from: https://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p156.pdf.
[2] Centeno CC, Dourado MC, Penso LD, Rautenbach D, Szwarcfiter JL. Irreversible Conversion of Graphs. Theor Comput Sci. 2011; 412: 3693-3700. DOI: https://doi.org/10.1016/j.tcs.2011.03.029.
[3] Dreyer PA., Jr, Roberts FS. Irreversible k-threshold processes: Graph theoretical threshold models of the spread of disease and of opinion. Discret Appl Math. 2009; 157(7): 1615-1627. DOI: https://doi.org/10.1016/j.dam.2008.09.012.
[4] Frances MD, Mynhardt CM, Wodlinger JL. Subgraph-avoiding minimum decycling sets and k-conversion sets in graphs. Australas J Comb. 2019; 74(3): 288-304. Available from: https://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p288.pdf
[5] Gagnon A, Hassler A, Huang J, Krim-Yee A, Inerney FM, Zacarias AM, Seamone B, Virgile V. A method for eternally dominating strong grids. Discret Math Theor Comput Sci 2020; 22(1): 1j+. DOI: https://doi.org/10.23638/DMTCS-22-1-8.
[6] KlobucΜar A. Independent sets and independent dominating sets in the strong product of paths and cycles. Math Commun. 2005; 10(1): 23-30. Available from: https://hrcak.srce.hr/file/1331.
[7] KyncΜl J, LidickyΜ B, VyskocΜil T. Irreversible 2-conversion set in graphs of bounded degree. Discret Math Theor Comput Sci. 2017; 19(3): 81-89. DOI: https://doi.org/10.23638/DMTCS-19-3-5.
[8] Mynhardt CM, Wodlinger JL. A Lower Bound On The k-Conversion Number Of Graphs Of Maximum Degree k + 1. Trans Combin. 2019; 9(3): 1-12. DOI: http://dx.doi.org/10.22108/toc.2019.112258.1579.
[9] Mynhardt CM, Wodlinger JL. The k-conversion number of regular graphs, AKCE Int J Graphs Comb. 2020; 17(3): 955-965. DOI: https://doi.org/10.1016/j.akcej.2019.12.016.
[10] Shaheen R, Mahfud S, Kassem A. Irreversible k-Threshold Conversion Number of Circulant Graphs. J Appl Math. 2022; 2022: 14. 1250951. DOI: https://doi.org/10.1155/2022/1250951.
[11] Shaheen R, Mahfud S, Kassem A. Irreversible k-Threshold Conversion Number of Some Graphs. Arab Journal of Mathematical Sciences. 2022; Vol. ahead-of-print No. ahead-of-print. DOI: https://doi.org/10.1108/AJMS-07-2021-0150.
[12] Shaheen R, Mahfud S, Kassem A. Irreversible k-Threshold Conversion Number of the Strong Product of Two Paths when k=2,3. Tishreen University Journal for Research and Scientific Studies, Basic Science Series. 2022; 44(3): 67-82. Available from: http://journal.tishreen.edu.sy/index.php/bassnc/article/view/13249.
[13] Takaoka A, Ueno S. A Note on Irreversible 2-Conversion Sets in Subcubic Graphs. IEICE Trans Inf Syst. 2015; E98.D(8): 1589-91. DOI: https://doi.org/10.1587/transinf.2015EDL8021.
Cite This Article
Choose your preferred format