Probabilistic zero forcing with vertex reversion [r-libre/3897]

Morneau-Guérin, Frédéric (2025). Probabilistic zero forcing with vertex reversion [compte rendu de l'ouvrage de Brennan, Zachary]. zbMATH Open.

Fichier(s) associé(s) à ce document :

PDF - 08113571.pdf
Contenu du fichier : Version de l'éditeur

Télécharger

Catégorie de document :	Comptes rendus d'ouvrages
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	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. This 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. One such variant is probabilistic zero forcing (PZF), first introduced by C. X. Kang and 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: 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. 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. The 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. The paper also provides standard Markov-chain results for RPZF processes and associated parameters on arbitrary graphs.
Informations complémentaires :	© FIZ Karlsruhe GmbH 2025. ALL RIGHTS RESERVED.
Adresse de la version officielle :	https://zbmath.org/8113571
Déposant:	Morneau-Guérin, Frédéric
Responsable :	Frédéric Morneau-Guérin
Dépôt :	25 nov. 2025 20:21
Dernière modification :	25 nov. 2025 20:21

Actions (connexion requise)

RÉVISER