Irreversible \(k\)-threshold and majority conversion processes on complete multipartite graphs and graph products (Q2848721)

In an irreversible \(k\)-threshold conversion process, a vertex is permanently colored black in a certain time period if at least \(k\) of its neighbors were black in the previous time period. A \(k\)-conversion set is a set of vertices which, if initially colored black, will result in all vertices eventually being colored black under a \(k\)-threshold conversion process. This is similarly defined for majority conversion process. The paper determines the exact values or upper bounds for the minimum number of vertices in \(k\)-conversion sets of a graph. Previously, the exact values of this minimum number have been found for all \(k\) when the graph is a path, cycle, complete multipartite graph or tree. In addition, some exact values and upper bounds of this number are known for certain values of \(k\) when the graph is planar, cylindrical, or toroidal square grid.