Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule , and to the combinatorial transversal relation between the families of inclusion-minimal -forcing and -immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their -immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part ( -PUSH, -PUSH, -PUSH, -PULL, -PULL, and -wPULL), we prove the -Completeness of the decision problem associated to the corresponding -immune number of the graph.

Partially supported by the Ministerio de Ciencia e Innovaci´on/Agencia Estatal de Investigaci´on, Spain, and the European Regional Development Fund under project PGC2018- 095471-B-I00; and by AGAUR from the Catalan Government under project 2017SGR–1087.

© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/

Peer Reviewed