Irreversible k-Threshold Conversion Number of Strong Grids for k3

Ali Hasan Ali, Ramy Shaheen, Suhail Mahfud · 2024

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 𝑚,𝑛.

Read the paper · More papers on PaperTik