Probabilistic zero forcing with vertex reversion (Q6908467)

Suppose a graph is colored so that every vertex is either blue or white. The (deterministic) zero forcing color-change rule describes how blue vertices infect neighboring white vertices: a blue vertex \(u\) forces (changes) a white neighbor \(w\) to blue if \(w\) is its unique white neighbor.\N\NThis coloring process was introduced independently as a tool for controlling quantum systems and as a bound on the maximum nullity of a matrix in the study of the minimum rank problem. Since then, zero forcing has been found to have links with graph-search algorithms, power domination, and the Cops and Robbers game. It has thus become a topic of interest in its own right, giving rise to several variants.\N\NOne such variant is probabilistic zero forcing (PZF), first introduced by \textit{C. X. Kang} and \textit{E. Yi} [Bull. Inst. Comb. Appl. 67, 9--16 (2013; Zbl 1274.05475)] and forming the foundation of the present paper. Building on PZF, the author introduces reversion probabilistic zero forcing (RPZF), a modification in which blue vertices may revert to white at the end of each round. Two versions of this process are defined:\N\N\begin{itemize}\N\item[1.] Single absorption reversion probabilistic zero forcing (SARPZF). In each round, phase 1 consists of each blue vertex independently attempting to force each of its white neighbors, with success governed by a fixed forcing probability; in phase 2, each blue vertex independently attempts to revert to white, again according to a prescribed reversion probability.\N\N\item[2.] Dual absorption reversion probabilistic zero forcing (DARPZF). This variant modifies the SARPZF rule by adding one restriction: after the probabilistic forcing attempts of phase 1, if all vertices have become blue, then no probabilistic reversion occurs in phase 2 -- in other words, the reversion step is suppressed whenever the graph becomes fully blue.\N\end{itemize}\N\NThe main results of the paper describe the behavior of RPZF on complete and complete bipartite graphs under various initial densities of infected vertices. Quantities such as the threshold number of initially infected vertices required to fully infect the graph in a single time step, as well as asymptotic behavior, are analyzed. It is also shown that the star graph is comparatively more difficult to fully infect than complete or balanced complete bipartite graphs, a notion explored further through simulations.\N\NThe paper also provides standard Markov-chain results for RPZF processes and associated parameters on arbitrary graphs.