Volume 11 β’ Issue 2 β’ PP: 60-72 β’ 2024
Irreversible k-Threshold Conversion Number of Strong Grids for k>3
Open Access & Copyright
Β© 2024 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
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
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.