Volume 25 • Issue 2 • PP: 183-196 • 2025
On the Irreversible k-Threshold Conversion Number for Some Graph Products and Neutrosophic Graphs
View PDF Abstract
An irreversible k-threshold conversion process on a graph G=(V,E) is an iterative process that studies the spread of a one way change (from state 0 to 1) on V(G). The process begins by choosing a set S_0⊆V. For each step t(t=1,2,…,), S_t is obtained from S_(t-1) by adjoining all vertices that have at least k neighbors in S_(t-1). We call S_0 the seed set of the k-threshold conversion process and if S_t=V(G) for some t≥0, then S_0 is called an irreversible k-threshold conversion set (IkCS) of G. The k-threshold conversion number of G (denoted by (c_k (G)) is the minimum cardinality of all the IkCSs of G. In this paper, we study IkCSs of toroidal grids and the tensor product of two paths. We determine c_2 (C_3×C_n ) and we present upper and lower bounds for c_2 (C_m×C_n) for m,n≥3. We also determine c_2 (P_2×P_n ),c_2 (P_3×P_n ) and present an upper bound for c_2 (P_m×P_n) when m,n>3. Then we determine c_3 (P_m×P_n) for m=2,3,4 and arbitrary n. Finally, we determine c_4 (P_m×P_n) for arbitrary m,n. . Also, we study the same concepts over some neutrosophic graphs with suggestions for future neutrosophic and fuzzy generalizations.
Keywords
References
[1] Adams S.S,BrassZ.,StokesC.,and Troxell D.S.,(2015).Irreversible k-threshold and majority conversion processes on complete multipartite graphs and graph products, Australasian Journal of Combinatorics. (6)1156- 174. https://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p156.pdf.
[2] Centeno C. C.,Dourado M. C., Penso L. D., Rautenbach D and Szwarcfiter J L, (2011) . Irreversible conversion of graphs, Theoretical Computer Science. 412 3693-3700. (DOI: https://doi.org/10.1016/j.tcs.2011.03.029 ).
[3] Dreyer, Jr P A. and Roberts F S., (2009). Irreversible k-threshold processes: Graph theoretical threshold models of the spread of disease and of opinion, Discrete Applied Mathematics. 157(7) 615-1627.(DOI: https://doi.org/10.1016/j.dam.2008.09.012 ).
[4] Frances M D, Mynhardt C M and Wodlinger J L, (2019). Subgraph-avoiding minimum decycling sets and k-conversion sets in graphs, Australasian Journal of Combinatorics. 74(3) 288-304. https://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p288.pdf.
[5] Harary F, Graph Theory, Addison-Wesley, Reading Mass (1969).
[6] Jha P K and Klav ar S., (1998). Independence in direct-product graphs, Ars Combin. 50 53-63.
[7] Hatamleh, R. (2003). On the Form of Correlation Function for a Class of Nonstationary Field with a Zero Spectrum. Rocky Mountain Journal of Mathematics, 33(1)159-173. https://doi.org/10.1216/rmjm/1181069991.
[8] Kyn l J, Lidicky B. and Vysko il T., (2017). Irreversible 2-conversion set in graphs of bounded degree, Discrete Mathematics & Theoretical Computer Science, 19(3) 81-89. (DOI: https://doi.org/10.23638/DMTCS-19-3-5).
[9] Hatamleh, R., Zolotarev,V.A. (2014). On Two-Dimensional Model Representations of One Class of Commuting Operators. Ukrainian Mathematical Journal, 66(1), 122–144. (Doi:https://doi.org/10.1007/s11253-014-0916-9).
[10] Mynhardt C M and Wodlinger J L,(2019).Alower bound on the k-conversion number of graphs of maximum degree k + 1, Transactions on Combinatorics. 9(3) 1-12.(DOI: http://dx.doi.org/10.22108/toc.2019.112258.1579).
[11] Hatamleh, R., Zolotarev,V.A.(2016). Triangular Models of Commutative Systems of Linear Operators Close to Unitary Operators. Ukrainian Mathematical Journal, 68(5), 791–811. (Doi: https://doi.org/10.1007/s11253-016-1258-6).
[12] Mynhardt C M and Wodlinger J L, (2020). The k-conversion number of regular graphs, AKCE International Journal of Graphs and Combinatorics. 17(3) 955-965, (DOI:https://doi.org/10.1016/j.akcej.2019.12.016).
[13] Shaheen R, Mahfud S and Kassem A, Irreversible k-Threshold Conversion Number of Circulant Graphs. Submitted.
[14] Takaoka A and Ueno S., ((2015).A note on irreversible 2-conversion sets in subcubic graphs, IEICE Transactions on Information and Systems. E98.D (8) 1589–1591. (Doi : https://doi.org/10.1007/a13278-012-0067-7).
[15] Wang T M., (2005). Toroidal grids are anti-magic, Computing and Combinatorics, Lecture Notes in Comput. Sci, 3595, Springer, Berlin, 671-679. (Doi: https://link.springer.com/chapter/10.1007/11533719_68 ).
[16] Heilat, A.S., Batiha,B ,T.Qawasmeh ,Hatamleh R.(2023). Hybrid Cubic B-spline Method for Solving A Class of Singular Boundary Value Problems. European Journal of Pure and Applied Mathematics, 16(2), 751-762. (DOI: https://doi.org/10.29020/nybg.ejpam.v16i2.4725).
[17] T.Qawasmeh,R.Hatamleh,(2023).A new contraction based on H-simulation functions in the frame of extended b-metric spaces and application,International Journal of Electrical and Computer Engineering 13 (4),4212- 4221.
[18] Ayman Hazaymeh, Rania Saadeh, Raed Hatamleh, Mohammad W Alomari, Ahmad Qazza. (2023). A Perturbed Milne’s Quadrature Rule for n-Times Differentiable Functions with Lp-Error Estimates, Axioms-MDPI,12(9),803.
[19] Ayman Hazaymeh, Ahmad Qazza, Raed Hatamleh,Mohammad W. Alomari,Rania Saadeh.(2023). On Further Refinements of Numerical Radius Inequalities. Axiom-MDPI,12(9),807.
[20] Batiha, B., Ghanim, F., Alayed, O., Hatamleh, R., Heilat, A. S., Zureigat, H., & Bazighifan, O. (2022). Solving Multispecies Lotka–Volterra Equations by the Daftardar-Gejji and Jafari Method. International Journal of Mathematics and Mathematical Sciences, 2022, 1–7. (Doi: https://doi.org/10.1155/2022/1839796).
[21] Al-Husban, A., Al-Qadri, M. O., Saadeh, R., Qazza, A., & Almomani, H. H. (2022). Multi-fuzzy rings. WSEAS Trans. Math, 21, 701-706.
[22] Hamadneh, T., Hioual, A., Alsayyed, O., Al-Khassawneh, Y. A., Al-Husban, A., & Ouannas, A. (2023). The FitzHugh–Nagumo Model Described by Fractional Difference Equations: Stability and Numerical Simulation. Axioms, 12(9), 806.
[23] Al-Husban, A. B. D. U. L. L. A. H., Al-Sharoa, D. O. A. A., Al-Kaseasbeh, M. O. H. A. M. M. A. D., & Mahmood, R. M. S. (2022). Structures of fibers of groups actions on graphs. WSEAS Trans. Math, 7, 650-658.
[24] AL-HUSBAN, A. B. D. A. L. L. A. H., AL-SHAROA, D. O. A. A., SAADEH, R., QAZZA, A., & MAHMOOD, R. (2023). ON THE FIBERS OF THE TREE PRODUCTS OF GROUPS WITH AMALGAMATION SUBGROUPS. Journal of applied mathematics & informatics, 41(6), 1237-1256.
Cite This Article
Choose your preferred format