# Spreading in graphs

Boštjan Brešara,b, Tanja Draveca,b, Aysel Ereyc, and Jaka Hedžetb,a

###### Abstract

Several concepts that model processes of spreading (of information, disease,
objects, etc.) in graphs or networks have been studied. In many contexts, we
assume that some vertices of a graph $G$ are contaminated initially, before
the process starts. By the $q$-forcing rule, a contaminated vertex having at
most $q$ uncontaminated neighbors enforces all the neighbors to become
contaminated, while by the $p$-percolation rule, an uncontaminated vertex
becomes contaminated if at least $p$ of its neighbors are contaminated. If
given a set $S$ of initially contaminated vertices all vertices eventually
become contaminated when continuously applying the $q$-forcing rule
(respectively the $p$-percolation rule), $S$ is called a $q$-forcing set
(respectively, a $p$-percolating set) in $G$. In this paper, we consider sets
$S$ that are at the same time $q$-forcing sets and $p$-percolating sets, and
call them $(p,q)$-spreading sets. Given positive integers $p$ and $q$, the
minimum cardinality of a $(p,q)$-spreading set in $G$ is a $(p,q)$-spreading
number, $\sigma_{(p,q)}(G)$, of $G$. While $q$-forcing sets have been studied
in a dozen of papers, the decision version of the corresponding graph
invariant has not been considered earlier, and we fill the gap by proving its
NP-completeness. This, in turn, enables us to prove the NP-completeness of the
decision version of the $(p,q)$-spreading number in graphs for an arbitrary
choice of $p$ and $q$. Again, for every $p\in\mathbb{N}$ and
$q\in\mathbb{N}\cup\\{\infty\\}$, we find a linear-time algorithm for
determining the $(p,q)$-spreading number of a tree, where in the case $p\geq
2$ we apply Riedl’s algorithm from [Largest and smallest minimal percolating
sets in trees, Electron. J. Combin. 19 (2012) Paper 64] on $p$-percolation in
trees. In addition, we present a lower and an upper bound on the
$(p,q)$-spreading number of a tree and characterize extremal families of
trees. In the case of square grids, we combine some results of Bollobás from
[The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New
York, 2006], and the AIM Minimum Rank-Special Graphs Work Group from [Zero
forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 2008
1628–1648], and new results on $(2,1)$-spreading and $(4,q)$-spreading to
obtain $\sigma_{(p,q)}(P_{m}\Box P_{n})$ for all
$(p,q)\in(\mathbb{N}\setminus\\{3\\})\times(\mathbb{N}\cup\\{\infty\\})$ and
all $m,n\in\mathbb{N}$.

a Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

c Department of Mathematics and Statistics, Utah State University, USA

Keywords: bootstrap percolation, zero forcing, tree, grid

AMS Subj. Class.: 05C35, 05C75, 05C85

##  1 Introduction

Zero forcing was independently introduced by mathematical physicists in the
study of quantum systems [9] and by linear algebraists in connection with the
maximum nullity of real symmetric matrices [2]. Since then, zero forcing
received a lot of attention by graph theorists; see [7, 14, 18, 19] for some
recent papers and the monograph [17] that surveys various studies of zero
forcing. The notion of zero forcing appears also in the analysis of the
diverse processes, in which the need of uniform framework led to the
introduction of the generalization of zero forcing named $k$-forcing [3].

Suppose that vertices of a graph $G$ are assigned one of the two possible
colors, white and blue. The color change rule in $k$-forcing is defined as
follows: if a blue vertex $u$ has at most $k$ white neighbors, then change
color of all white neighbors of $u$ to blue. In particular, when $k=1$, this
is the color change rule for zero forcing. If for a set of vertices
$S\subseteq V(G)$, which are initially colored blue, continuous application of
the color change rule enforces all vertices of $G$ to become blue, then $S$ is
a $k$-forcing set of $G$ (resp., a zero forcing set of $G$ when $k=1$). The
$k$-forcing number of $G$, $F_{k}(G)$, is the minimum cardinality of a
$k$-forcing set of $G$, while the zero forcing number, when $k=1$, is denoted
by $Z(G)$, and so $Z(G)=F_{1}(G)$.

The concept of bootstrap percolation has a similar definition to that of zero
forcing, yet a different motivation. It was introduced as a simplified model
of a magnetic system in 1979 [11], and was later studied on random graphs and
also on deterministic graphs. Let us mention that one of the first graphs in
which bootstrap percolation was studied were grids [5, 6].

Again let all vertices of a graph $G$ be colored either white or blue. (In
some applicable contexts, blue vertices are called “infected” and white
vertices “uninfected”.) A set $S\subseteq V(G)$ of blue vertices is an
$r$-neighbor bootstrap percolating set, or simply, an $r$-percolating set of
$G$ if by repeatedly applying the rule: if a white vertex $u$ has at least $r$
blue (infected) neighbors, then change color of $u$ to blue, all vertices of
$G$ eventually become blue. The $r$-neighbor bootstrap percolation number of
$G$, $m(G,r)$, is the minimum cardinality of an $r$-neighbor bootstrap
percolating set of $G$.

Motivated by the similarity of the definitions of the above two concepts, we
introduce a common generalization of $k$-forcing and bootstrap percolation.
Let $p\in\mathbb{N}$ and $q\in\mathbb{N}\cup\\{\infty\\}$, and let vertices of
a graph $G$ be colored either white or blue. If a white vertex $w$ has at
least $p$ blue neighbors, and one of the blue neighbors of $w$ has at most $q$
white neighbors, then by the spreading color change rule the color of $w$ is
changed to blue. A set $S$ is a $(p,q)$-spreading set for $G$ if initially
exactly the vertices of $S$ are colored blue and by repeatedly applying the
spreading color change rule all the vertices of $G$ are eventually turned to
blue. The $(p,q)$-spreading number, ${\sigma_{(p,q)}}(G)$, of a graph $G$ is
the minimum cardinality of a $(p,q)$-spreading set.

The aim of this paper is to initiate the study of spreading in graphs. The
paper is organized as follows. In the next section, we specify connections
with some specializations of $(p,q)$-spreading, such as bootstrap percolation,
$P_{3}$-convexity and $q$-forcing. We also give some basic preliminary
results. In Section 3, we concentrate on complexity issues regarding the
computation of the $(p,q)$-spreading number. We prove that the decision
version of determining ${\sigma_{(p,q)}}(G)$, where $G$ is an arbitrary graph,
is an NP-complete problem. We do this by translating the decision version of
determining the $q$-forcing number of $G$, for which we also prove that it is
NP-complete. The latter result was, to the best of our knowledge, not known
before. In Section 4, we consider spreading in trees. First, we present
several algorithms to compute ${\sigma_{(p,q)}}(T)$, where $T$ is a tree. We
prove that $F_{q}(T)$ equals the size of a smallest partition of $T$ into
induced subtrees of maximum degree at most $q$, which enables us to present a
linear-time algorithm to determine $\sigma_{(1,q)}(T)$ for a tree $T$ and
$q\in\mathbb{N}$. We also note that Riedl’s algorithm [22], which computes the
$p$-neighbor bootstrap percolation of a tree in linear time, where $p\geq 2$,
works for any $q\in\mathbb{N}$. Second, we also find an upper and a lower
bound for the $(p,q)$-spreading number of a tree and characterize the trees
that attain these bounds. Section 5 is devoted to spreading in square grids.
By combining some known results (say, about the 2-neighbor bootstrap
percolation in grids due to Bollobás [6]) with some new results, we obtain the
$(p,q)$-spreading number of all grids for all $p$ and $q$ with the sole
exception when $p=3$. Finally, we state some concluding remarks and propose
several open problems in Section 6.

In the rest of this section, we present the notation used throughout the
paper. All graphs considered in this paper are finite, simple, and undirected.
Let $[n]=\\{1,2,\ldots,n\\}$, where $n\in\mathbb{N}$. For a graph $G=(V,E)$
and $S\subseteq V(G)$ we write $G[S]$ for the subgraph of $G$ induced by $S$.
The neighborhood of $v\in V(G)$, $N_{G}(v)$, is the set of all vertices in $G$
adjacent to $v$.

Similarly, for $S\subseteq V(G)$ and $v\in V(G)$, we let $N_{S}(v)=\\{u\in
S;vu\in E(G)\\}$. The degree of a vertex $v$ is deg${}_{G}(v)=|N_{G}(v)|$, and
$\Delta(G)=\max{\\{\textrm{deg}_{G}(v);v\in
V(G)\\}},\delta(G)=\min{\\{\textrm{deg}_{G}(v);v\in V(G)\\}}$. For $u,v\in
V(G)$, $d_{G}(u,v)$ denotes the length of a shortest $u,v$-path in $G$. For
$v\in V(G)$ and a subgraph $H\subseteq G$ of a graph $G$,
$d_{G}(u,H)=\min{\\{d_{G}(u,v);v\in V(H)\\}}.$ A subset of vertices $S$ is
called a vertex cover of $G$ if every edge of $G$ has an end-vertex in $S$.

The Cartesian product $G\,\square\,H$ of graphs $G$ and $H$ is defined as the
graph with $V(G\,\square\,H)=V(G)\times V(H)$, and
$(g,h)(g^{\prime},h^{\prime})\in E(G\,\square\,H)$ if either ($g=g^{\prime}$
and $hh\in E(H)$) or ($gg^{\prime}\in E(G)$ and $h=h^{\prime}$).

##  2 Preliminary results

$p$ | $q$ |  $(p,q)$-spreading
---|---|---
$1$ | $1$ | zero-forcing
$1$ | $q$ |  $q$-forcing
$p$ | $\infty$ |  $p$-bootstrap percolation
$2$ | $\infty$ |  $P_{3}$-convexity
Table 1: Specializations of $(p,q)$-spreading.

Note that $(p,q)$-spreading is a common generalization of bootstrap
percolation and zero forcing. The $(1,k)$-spreading number is exactly the
$k$-forcing number and the $(r,\infty)$-spreading number is exactly the
$r$-neighbor bootstrap percolation number. For $r=2$ this is also identical to
the concept that arises from $P_{3}$-convexity known as the $P_{3}$-hull
number (see [8, 10] for more on this concept), so the $(2,\infty)$-spreading
number is at the same time the 2-bootstrap percolation number and the
$P_{3}$-hull number. Table 1 presents these connections.

By the definition of the $(p,q)$-spreading number we immediately get the
following observations.

###### Remark 2.1

Let $G=(V,E)$ be a graph with maximum degree $\Delta$ and let $S$ be a
$(p,q)$-spreading set of $G$. The following statements hold;

  1. (1)

if $\deg(v)<p$ then $v\in S$;

  2. (2)

if $\Delta<p$ then ${\sigma_{(p,q)}}(G)=|V(G)|$;

  3. (3)

if $\Delta\leq q$ then ${\sigma_{(p,q)}}(G)=\sigma_{(p,\infty)}(G)$;

  4. (4)

${\sigma_{(p,q)}}(G)\geq\min{\\{p,|V(G)|\\}}$;

  5. (5)

$S$ is a $(p,q+1)$-spreading set, and
${\sigma_{(p,q)}}(G)\geq\sigma_{(p,q+1)}(G)$;

  6. (6)

$S$ is a $(p-1,q)$-spreading set, and
${\sigma_{(p,q)}}(G)\geq\sigma_{(p-1,q)}(G)$.

Next, we determine the $(p,q)$-spreading numbers in some basic graph classes
for any $p\in\mathbb{N}$ and any $q\in{\mathbb{N}}\cup\\{\infty\\}$. Since
$\Delta(P_{n})=\Delta(C_{n})=2$, Remark 2.1(2) implies that
${\sigma_{(p,q)}}(P_{n})={\sigma_{(p,q)}}(C_{n})=n$ for $p>2$. For $p=1$,
$\sigma_{(1,q)}(P_{n})=F_{q}(P_{n})=1$ and for $q\geq 2$,
$\sigma_{(2,1)}(P_{n})\geq\sigma_{(2,q)}(P_{n})=\sigma_{(2,\infty)}(P_{n})=m(P_{n},2)=\lceil\frac{n+1}{2}\rceil$
by Remark 2.1(3) and (5). For $q\geq 2$ we again easily deduce that
$\lceil\frac{n+1}{2}\rceil=\sigma_{(2,1)}(C_{n})\geq\sigma_{(2,q)}(C_{n})=m(C_{n},2)=\lceil\frac{n}{2}\rceil$.
In addition,

$\sigma_{(1,q)}(C_{n})=F_{q}(C_{n})=\begin{cases}2&\text{if }q=1\\\ 1&\text{if
}q>1.\end{cases}$

The spreading number can be easily computed also for complete graphs. It holds

${\sigma_{(p,q)}}(K_{n})=\begin{cases}p&\text{if }p+q\geq n\\\ n-q&\text{if
}p+q<n.\end{cases}$

Finally, the $(p,q)$-spreading number of a complete bipartite graph $K_{r,s}$
with $r\geq s$, depends on the relation between $p,q,r$ and $s$. For example,
if $s<p\leq r$, then we get

${\sigma_{(p,q)}}(K_{r,s})=\begin{cases}r&\text{if }q\geq s\\\ r+s-q&\text{if
}q<s.\end{cases}$

We end the section with a trivial result that will be needed later.

###### Lemma 2.2

Every $(p,q)$-spreading set $S$ contains a vertex $v$ such that

$|N_{S}(v)|\geq\deg_{G}(v)-q.$

Proof.  If every vertex in $S$ has more than $q$ neighbors outside $S$, then
$S$ cannot be a $(p,q)$-spreading set, since the color change rule cannot
begin. $\square$

##  3 NP-completeness

Given a graph $G$ and positive integers $p$ and $q$, the optimization version
of the $(p,q)$-spreading problem is to find a $(p,q)$-spreading set of minimum
size in $G$. The decision version of the problem can be formulated as follows:

$(p,q)$-Spreading Input: A graph $G=(V,E)$ and positive integers $p,q$ and $k$
Question: Is there a $(p,q)$-spreading set in $G$ of size at most $k$?

A special case of $(p,q)$-spreading problem is obtained when we set $p=1$, in
which case $(p,q)$-spreading, which is then $(1,q)$-spreading, coincides with
$q$-forcing. For some earlier studies of $q$-forcing see [3, 15, 20]. The
corresponding graph invariant, the $q$-forcing number of a graph $G$, is
denoted by $F_{q}(G)$ and equals ${\sigma_{(1,q)}}(G)$. We will deal with this
version of the problem separately, and formulate the corresponding decision
problem as follows:

$q$-Forcing Input: A graph $G=(V,E)$ and positive integers $q$ and $k$
Question: Is there a $q$-forcing set in $G$ of size at most $k$?

It is clear that both problems are in NP, and it suffices to argue this for
the $(p,q)$-Spreading problem. Let $G$ be a graph, and $p,q$ be positive
integers. If a set $S$ of size $k$ is presented to us, then we can clearly
check in polynomial time whether $S$ is a $(p,q)$-spreading set in $G$.

First, we prove NP-completeness of the $q$-Forcing problem. We will use a
translation of the well-known zero forcing problem, which was proven to be NP-
complete in [1]. Note that the zero forcing problem is simply the $q$-forcing
problem for $q=1$. The standard notation for the zero forcing number of a
graph $G$ is $Z(G)$.

We need the following definition. Let $G=(V,E)$ be a graph and $S$ a
$q$-forcing set of $G$. Then by definition, before the $q$-forcing process
starts vertices of $S$ are blue, vertices of $V(G)-S$ are white and the
$q$-forcing procedure recolors all vertices of $V(G)-S$ to blue. In
particular, in the $i$th step of this procedure, by the $q$-forcing rule,
there exists a blue vertex $a_{i}\in V(G)$ whose white neighbors are vertices
$x_{1}^{i},\ldots,x_{q_{i}}^{i}$, where $1\leq q_{i}\leq q$, and $a_{i}$
forces vertices $x_{1}^{i},\ldots,x_{q_{i}}^{i}$ to become blue. Let us denote
the corresponding $q$-forcing sequence $(a_{1},\ldots,a_{k})$ by $Z$ and
denote by $f_{Z}$ the function which maps each $a_{i}\in Z$ to the subset
$\\{x_{1}^{i},\ldots,x_{q_{i}}^{i}\\}$ of $V(G)$.

Let $G=(V,E)$ be a graph with $V(G)=\\{v_{1},\ldots,v_{n}\\}$. We define the
graph $G^{*}$ constructed from $G$ as follows. For any vertex $v_{i}\in V(G)$
add vertices $a_{1}^{i},\ldots,a_{q-1}^{i}$,
$b_{1}^{i},\ldots,b_{q}^{i},c_{1}^{i}\ldots,c_{q}^{i}$ and edges
$v_{i}a_{j}^{i}$ for any $j\in[q-1]$ and all possible edges between vertices
in $A^{i}\cup B^{i}$ and all possible edges between vertices in $B^{i}\cup
C^{i}$, where
$A^{i}=\\{a_{1}^{i},\ldots,a_{q-1}^{i}\\},B^{i}=\\{b_{1}^{i},\ldots,b_{q}^{i}\\},C^{i}=\\{c_{1}^{i}\ldots,c_{q}^{i}\\}$.
Hence the subgraph of $G^{*}$ induced by $A^{i}\cup B^{i}$ is isomorphic to
the complete graph $K_{2q-1}$ and the subgraph of $G^{*}$ induced by
$B^{i}\cup C^{i}$ is isomorphic to $K_{2q}$. Denote by $H_{i}$ the subgraph of
$G^{*}$ induced by $A^{i}\cup B^{i}\cup C^{i}$.

###### Lemma 3.1

If $G$ is a graph and $q\geq 2$ an integer, then $F_{q}(G^{*})=Z(G)$.

Proof. First, we will show that if $S$ is a zero forcing set of $G$, then $S$
is also a $q$-forcing set of $G^{*}$. If a blue vertex in $V(G)$ has at most
one white neighbor in $G$, then it has at most $q$ white neighbors in $G^{*}$.
Therefore, if a white vertex in $G$ becomes blue according to zero-forcing
rule in $G$, then it becomes blue according to $q$-forcing rule in $G^{*}$ as
well. It follows that $S$ forces all vertices in $V(G)$ to become blue
according to $q$-forcing rule in $G^{*}$. After all vertices in $V(G)$ become
blue, each vertex $v_{i}$ has at exactly $q-1$ white neighbors and so, each
$v_{i}$ forces all vertices in $A^{i}$ to become blue according to $q$-forcing
rule in $G^{*}$. Now, each vertex in $A_{i}$ has at most $q$ white neighbors.
Therefore, any vertex in $A_{i}$ forces all vertices in $B_{i}$ to become blue
according to $q$-forcing rule in $G^{*}$. Similarly, after all vertices in
$B_{i}$ become blue, each vertex in $B_{i}$ has at most $q$ white neighbors.
Therefore, any vertex in $B_{i}$ forces all vertices in $C_{i}$ to become
blue. This implies that $S$ is a $q$-forcing set of $G^{*}$ and thus
$F_{q}(G^{*})\leq Z(G)$.

Now, let $S^{*}$ be a minimum $q$-forcing set of $G^{*}$ such that $\sum_{s\in
S^{*}}d_{G^{*}}(s,G)$ is the smallest possible. Denote $S^{*}_{i}=S^{*}\cap
V(H_{i})$ and let $Z^{*}=(x_{1},\ldots,x_{k})$ be a $q$-forcing sequence of
$G^{*}$.

###### Claim 1

For any $i\in[n]$: $|S^{*}_{i}|\leq q-1$ and $S^{*}\cap(B^{i}\cup
C^{i})=\emptyset$.

Proof. For the purpose of contradiction assume that $|S^{*}_{i}|\geq q$. Then
$S^{\prime}=(S^{*}-S^{*}_{i})\cup A^{i}\cup\\{v_{i}\\}$ is a $q$-forcing set
of $G^{*}$ with $\sum_{s\in S^{*}}d_{G^{*}}(s,G)>\sum_{s\in
S^{\prime}}d_{G^{*}}(s,G)$, a contradiction.

Since $|S^{*}_{i}|\leq q-1$ the set $S^{\prime}$, obtained from $S^{*}$ by
replacing each vertex in $B^{i}\cup C^{i}$ by one vertex in $A^{i}$, is also a
$q$-forcing set of $G^{*}$. If $(B^{i}\cup C^{i})\cap S_{i}^{*}\neq\emptyset$,
then $S^{\prime}$ has a smaller sum of distances to $G$ than $S^{*}$ which
contradicts with the definition of $S^{*}$. Thus, $(B^{i}\cup C^{i})\cap
S_{i}^{*}=\emptyset$.

$(\square)$

By Claim 1, $S^{*}\subseteq V(G)\cup A^{1}\cup\ldots\cup A^{n}$.

###### Claim 2

If $j$ is the smallest index such that $x_{j}\in V(H_{i})$ for some $i\in[n]$,
then $x_{j}\in A^{i}$ and $v_{i}\notin f_{Z^{*}}(x_{j})$.

Proof. By Claim 1, $S^{*}_{i}\cap(B^{i}\cup C^{i})=\emptyset$, hence vertices
in $B^{i}$ can become blue just if all vertices from $A^{i}$ are already blue,
which implies that a vertex from $A^{i}$ will force vertices in $B^{i}$ and
then vertex in $B^{i}$ will force vertices in $C^{i}$ to become blue. Hence
$x_{j}\in A^{i}$, i.e. $x_{j}=a_{m}^{i}$ for some $m\in[q-1].$

Suppose that at this step of $q$-forcing procedure $v_{i}$ is one of at most
$q$ white neighbors of $x_{j}=a_{m}^{i}$. Hence at least $q$ vertices of
$A^{i}\cup B^{i}$ are blue at this step. Since by Claim 1, $|S^{*}_{i}|\leq
q-1$, we get a contradiction with the fact that $a_{m}^{i}$ is the first
vertex of $Z^{*}$ that is also in $H^{i}$.  $(\square)$

Claim 2 implies that $v_{i}$ is already blue when the $q$-forcing rule is
performed by $x_{j}$. By using $Z^{*}$ we will construct a zero forcing
sequence $Z$ in $G$. In particular, we will show that $Z$ can be obtained from
$Z^{*}$ by removing from $Z^{*}$ only the vertices from $G^{*}$ that are not
in $G$.

Suppose that we are in step $j$ of the $q$-forcing procedure in $G^{*}$, where
blue vertex $x_{j}$ in $Z^{*}$ will force its white neighbors to become blue
($x_{j}$ has at most $q$ white neighbors). We will prove that if $x_{j}\in
V(G)$, then it has at most one white neighbor in $V(G)$, which will yield that
$Z$ is a zero-forcing sequence.

Thus let $x_{j}\in V(G)$. Hence there exists $i\in[n]$ such that
$x_{j}=v_{i}$. Let $A$ be the set of white neighbors of $v_{i}$ in $H_{i}$
after the first $j-1$ steps of the $q$-forcing procedure. Suppose to the
contrary that $A\neq A^{i}$, i.e. at least one vertex of $A^{i}$ is blue.
Vertices of $H_{i}$ that are blue after $j-1$ steps of the $q$-forcing
procedure are either from $S^{*}$ or they were colored blue in one of these
steps. If the latter holds, then by Claim 2, there exists a vertex $a_{t}^{i}$
from $A^{i}$ which is in $Z^{*}$ before $x_{j}$. By Claims 1 and 2 we infer
$S^{*}_{i}=A^{i}$. Hence all vertices of $A^{i}$ are blue before step $j$ of
the $q$-forcing procedure. Since by Claim 2 $v_{i}\notin
f_{Z^{*}}(a_{t}^{i})$, the set $S^{\prime}$ obtained from $S^{*}$ by replacing
a vertex from $A^{i}$ by one of $v_{i}$’s white neighbors in $G$ (which exists
because $v_{i}=x_{j}\in Z^{*}$ and has no white neighbors in $H_{i}$), is also
a $q$-forcing set of $G^{*}$. To see that $S^{\prime}$ is a $q$-forcing set
note that all the $q$-forcing rules in the first $j-1$ steps are preformed in
the same way as with $S^{*}$, except possibly within $H_{i}$. Anyway, after
$v_{i}$ forces its neighbors to become white, we can force the whole $H_{i}$
to become blue after at most two additional steps. The remaining steps, after
step $j$, follow exactly the same procedure as with $S^{*}$. Note that
$S^{\prime}$ has smaller sum of distances to $G$ than $S^{*}$, a
contradiction. Thus vertices of $H_{i}$ that are blue after the first $j-1$
steps of the $q$-forcing procedure are from $S^{*}$. In the same way as above,
the set $S^{\prime}$ obtained from $S^{*}$ by removing from $S^{*}$ a blue
vertex from $A^{i}$ and adding to $S^{\prime}$ one of $v_{i}$’s white
neighbors in $G$ (if it exists), is also a $q$-forcing set of $G^{*}$. Note
that it is possible that $v_{i}$ has no white neighbors in $G$ in which case
$S^{\prime}$ is smaller than $S^{*}$, a contradiction. Otherwise $S^{\prime}$
has smaller sum of distances to $G$ than $S^{*}$, again a contradiction. Hence
$A=A^{i}$, i.e. all vertices of $A^{i}$ are white before step $j$ of the
$q$-forcing procedure. Hence $x_{j}=v_{i}$ has at most one white neighbor in
$G$.

Hence the sequence $Z$ obtained from $Z^{*}$ by removing from $Z^{*}$ only the
vertices from $G^{*}$ that are not in $G$, is a zero forcing sequence. Thus
$S^{*}\cap V(G)$ is a zero forcing set which implies that $Z(G)\leq
F_{q}(G^{*})$. $\square$

###### Theorem 3.2

The $q$-Forcing problem is NP-complete.

In other words, the $(1,q)$-Spreading problem is NP-complete. We will now
translate this problem to the general $(p,q)$-Spreading problem, and show its
NP-completess.

###### Lemma 3.3

Let $G$ be a graph and let $p,q\in\mathbb{N}$ with $p\geq 2$. If $G^{\prime}$
is obtained from $G$ by adding vertices $u_{1},\ldots,u_{p-1}$, attaching $p$
leaves to each vertex $u_{i}$, and connecting each $u_{i}$ to every vertex of
$G$, then ${\sigma_{(p,q)}}(G^{\prime})=F_{q}(G)+p(p-1)$.

Proof. Let $S$ be a minimum $q$-forcing set of $G$. Set
$U=\\{u_{1},\ldots,u_{p-1}\\}$, and let $L$ be the set of all leaves in
$G^{\prime}$. (Note that $|L|=p(p-1)$.) Now, let $S^{\prime}=S\cup L$ be the
set of vertices that are initially set blue within the $(p,q)$-spreading
process in $G^{\prime}$. Note that the leaves in $L$ make their neighbors in
$U$ blue, because each $u_{i}$ has $p$ blue leaf-neighbors. Hence, each vertex
of $V(G)$ already has at least $p-1$ blue neighbors, and so the condition of
$(p,q)$-spreading that each white vertex must have at least $p$ neighbors is
fulfilled as soon as a white neighbor in $V(G)$ has a blue neighbor also in
$V(G)$. Thus, the process of changing colors with respect to the
$(p,q)$-spreading rules takes the same steps as the color change process with
respect to $q$-forcing in $G$. Hence, $S^{\prime}$ is a $(p,q)$-spreading set
in $G^{\prime}$, and we readily infer that ${\sigma_{(p,q)}}(G^{\prime})\leq
F_{q}(G)+p(p-1)$.

For the reversed inequality, let $S^{\prime}$ be a minimum $(p,q)$-spreading
set of $G^{\prime}$. Note that necessarily $L\subset S^{\prime}$, for
otherwise none of the leaves would ever become blue, because they each have at
most one neighbor and $p>1$. In addition, $U\cap S^{\prime}=\emptyset$,
because each $u_{i}$ becomes blue due to its $p$ leaf neighbors. Let
$S=S^{\prime}\cap V(G)$. By the same reasoning as in the previous paragraph,
we infer that $S$ is a $q$-forcing set of $G$. Indeed, the condition for a
white vertex having at least $p$ neighbors if fulfilled as soon as it has a
blue neighbor in $G$. Therefore only the condition of a blue neighbor having
at most $q$ white neighbors has to be considered, which is exactly the
$q$-forcing rule. Hence, $S$ is a $q$-forcing set of $G$, and so
$F_{q}(G)\leq{\sigma_{(p,q)}}(G^{\prime})-p(p-1)$. $\square$

Since the construction of $G^{\prime}$ from $G$ can be done in polynomial
time, we infer, by using also Lemma 3.3, that a polynomial solution of the
$(p,q)$-Spreading problem in $G^{\prime}$ yields a polynomial solution of the
$q$-Forcing problem in $G$. We derive the following result.

###### Theorem 3.4

The $(p,q)$-Spreading problem is NP-complete.

##  4 Trees

In this section, we first consider algorithmic issues concerning
$(p,q)$-spreading in trees. In particular, for all feasible values of $p$ and
$q$ we present efficient algorithms to obtain a minimum $(p,q)$-spreading set
of an arbitrary tree. Second, we consider upper and lower bounds for
${\sigma_{(p,q)}}(T)$, where $T$ is a tree, and characterize families of trees
that achieve these bounds.

###  4.1 Algorithms for $(p,q)$-spreading

The zero forcing problem on trees has been studied in several papers. It is
well known that the zero forcing number $Z(T)$ of a tree $T$ is equal to the
size of the smallest partition of the vertex set of the tree into induced
paths, which is denoted by $P(T)$; see [2, 13]. In this section, we generalize
this result to the context of $q$-forcing, for which we need the following
definition. Let $P_{q}(T)$ denote the size of the smallest partition of $V(T)$
into subsets inducing trees of maximum degree at most $q+1$. Recall that
$F_{q}(T)=\sigma_{(1,q)}(T)$, and by definition, $P(T)=P_{1}(T)$ and
$Z(T)=F_{1}(T)$.

###### Theorem 4.1

Let $T$ be a tree and $q\in\mathbb{N}$. Then $F_{q}(T)=P_{q}(T)$.

Proof.  First, let $S=\\{v_{1},\ldots,v_{k}\\}$ be an $F_{q}$-set of $T$. Then
a blue vertex can apply the color change rule only if it is adjacent to at
most $q$ white neighbors. For each $i\in[k]$ let $T_{i}=\\{v_{i}\\}$. Then
whenever a vertex $x$ from $T_{i}$ has at most $q$ white neighbors, by the
color change rule these white neighbors become blue and we add them to the set
$T_{i}$ (note that $x$ is not unique, but we may choose it arbitrarily).
Notice that since $T$ is a tree, the graphs induced by vertices in $T_{i}$ are
also trees. Finally when every vertex is colored blue, the obtained sets
$T_{1},\ldots,T_{k}$ form a partition of $T$ into induced trees of degree at
most $q+1$, which infers $F_{q}(T)\geq P_{q}(T)$.

Now let $P_{q}(T)=k$ and $\\{T_{1},T_{2},\ldots,T_{k}\\}$ be a smallest
partition into induced trees of degree at most $q+1$. Let $\mathcal{T}$ be a
graph defined as follows: $V(\mathcal{T})=\\{T_{1},T_{2},\ldots,T_{k}\\}$ and
$T_{i}T_{j}\in E(\mathcal{T})$ if and only if there exist vertices $u\in
T_{i}$, $v\in T_{j}$, such that $uv\in E(T)$. Then $\mathcal{T}$ is also a
tree. We will use induction on $k$ to show that there exists an $F_{q}$-set
$S$, such that $|S|=k$, therefore proving that $F_{q}(T)\leq|S|=P_{q}(T)$.
First, let $k=1$, thus $\mathcal{T}$ consists only of vertex $T_{1}$. Let
$S=\\{x\\}$ where $x$ is a leaf. Then immediately the parent of $x$ is colored
blue. Notice that since $\Delta(T)\leq q+1$, whenever a white vertex changes
color because of a blue neighbor, it can then have at most $q$ white
neighbors, therefore the process continues. Since $T$ is connected, this
implies that $\\{x\\}$ is an $F_{q}$-set.

For the induction step, let $k\geq 2$ and suppose that $S^{\prime}$ is an
$F_{q}$-set of cardinality $m$ for every tree $T^{\prime}$ with
$|P_{q}(T^{\prime})|=m<k$. Let $T_{k}$ be a leaf in $\mathcal{T}$ and let
$T_{k}T_{1}\in E(\mathcal{T})$. Furthermore, let $u_{k}$ be the vertex in
$T_{k}$, which is adjacent to a vertex $u_{1}\in V(T_{1})$. Let $x_{k}$ be a
leaf in $T_{k}$. A similar color change process as in the base case takes
place in $T_{k}$ \- newly colored vertices have at most $q$ white neighbors.
The only exception is vertex $u_{k}$. When $u_{k}$ becomes blue, it has at
most $q$ white neighbors in $T_{k}$ and also one neighbor in $T_{1}$.
Therefore it can have $q+1$ white neighbors in which case the process cannot
continue. However, note that $u_{k}$ is already blue. Now let
$T^{\prime}=T-V(T_{k})$. Then $|P_{q}(T^{\prime})|=k-1$ and by the induction
hypothesis, there exists an $F_{q}$-set $S^{\prime}$ of $T^{\prime}$, such
that $|S^{\prime}|=k-1$. We claim that $S=S^{\prime}\cup\\{x_{k}\\}$ is an
$F_{q}$-set of $T$. Indeed, we can start the color change process in $x_{k}$
and continue in $T_{k}$ until $u_{k}$ is colored by blue. Since $u_{k}$ is
blue and as $u_{k}u_{1}$ is the only edge between $T^{\prime}$ and $T_{k}$, we
can apply the same color changing process as in $T^{\prime}$ and color all
vertices of the subtree $T^{\prime}$ in $T$ to blue. Now, if at this point not
all vertices of $T_{k}$ are blue, we can simply continue by applying the color
change rule on $T_{k}$, because $u_{k}$ and its unique neighbor in
$T^{\prime}$ are already blue. In this way, also all vertices of $T_{k}$, and
thus all vertices of $T$ become blue. With this we proved that $S$ is an
$F_{q}$-set of $T$, and so $F_{q}(T)\leq P_{q}(T)$. $\square$

Next we will present an algorithm that computes $P_{q}(T)$ in a polynomial
time. Start with some notations and observations. Let $T$ be a tree. If
$\Delta(T)\leq q+1$, then $P_{q}(T)=1$. Thus we may assume that
$\Delta(T)>q+1$. We root $T$ in an arbitrary vertex $x_{0}$ which is the only
vertex at depth 0. Denote by $X_{1}$ all neighbors of $x_{0}$, i.e. all
vertices at depth 1 of the rooted tree $T$. Furthermore, for any $i>1$ denote
by $X_{i}$ the vertices at depth $i$ of the rooted tree $T$. Denote by $d$ the
depth of $T$, i.e. $V(T)=X_{0}\cup X_{1}\cup\ldots\cup X_{d}$. Moreover, for
$xy\in E(T)$, $x\in X_{i},y\in X_{i-1}$, denote by $T_{x}$ the connected
component of $T-y$ containing $x$.

Let $i$ be the largest index such that there exists a vertex $x_{i}\in X_{i}$
with $\deg(x_{i})>q+1$. If $i=0$, then $P_{q}(T)=\deg(x_{0})-q$. Otherwise
$x_{i}$ has exactly one neighbor, say $x_{i-1}$, in $X_{i-1}$ and $k>q$
neighbors $x_{i+1}^{1},\ldots,x_{i+1}^{k}$ in $X_{i+1}$. In any smallest
partition $\mathcal{P}$ of $T$ into induced trees of of maximum degree $q+1$,
neighbors of $x_{i}$ are in $k-q+1$ different trees of $\mathcal{P}$ (i.e.
$q+1$ neighbors of $x_{i}$ are in the same tree of $\mathcal{P}$). By the
choice of $i$, $\Delta(T_{x_{i+1}^{j}})\leq q+1$ for any
$j\in\\{1,\ldots,k\\}$. Thus there are at least $k-q-1$ indices $j$ such that
$T_{x_{i+1}^{j}}\in\mathcal{P}$.

Input: A rooted tree $T$ with vertices in $X_{i}$ at depth $i$.

Output: Smallest partition of $T$ into induced trees of maximum degree $q+1$.

1

2 $\mathcal{P}=\emptyset$;

3 while  _$T\neq\emptyset$_ do

4 if  _$\Delta(T)\leq q+1$_ then

5 $\mathcal{P}=\mathcal{P}\cup\\{T\\}$;

6 $T=\emptyset$;

7

8 else

9 $i:=$ the largest index such that there exists a vertex $x_{i}\in X_{i}$
with $\deg(x_{i})>q+1$;

10
${\mathcal{P}}={\mathcal{P}}\cup\\{T_{x_{i+1}^{q+2}},\ldots,T_{x_{i+1}^{k}}\\}\cup\\{T^{\prime}\\}$,
where $T^{\prime}$ is a subtree of $T$ induced by $\\{x_{i}\\}\cup
V(T_{x_{i+1}^{1}})\cup\ldots\cup V(T_{x_{i+1}^{q+1}})$;

11 $T:=T-T_{x_{i}}$;

12

13

Algorithm 1 Smallest partition of $T$ into induced trees of max-degree $q+1$.

###### Theorem 4.2

For any tree $T$, Algorithm 1 returns a smallest partition of $T$ into induced
trees of maximum degree $q+1$ and runs in linear time.

Proof.  Let $T$ be a tree rooted in an arbitrary vertex $x_{0}$ that is not a
leaf. Let $X_{i}$ be the set of vertices of $T$ at depth $i$. We will show
that a partition ${\mathcal{P}}$ of $T$ into induced trees of maximum degree
$q+1$ obtained by Algorithm 1 is a smallest such partition. The proof is by
induction on the number of vertices of $T$. If $T$ is any tree with
$\Delta(T)\leq q+1$, then the algorithm returns $\\{T\\}$ as the smallest
partition into trees of maximum degree at most $q+1$.

Assume now that $\Delta(T)>q+1$. If $T$ has a support vertex $y$ of degree at
most $q+1$, then let $x$ be a leaf neighbor of $y$ and $T^{\prime}=T-x$. Let
$\mathcal{P}$ be the partition of $T$ into induced trees of maximum degree
$q+1$ obtained by Algorithm 1 and let $T_{1}\in\mathcal{P}$ be the tree
containing $x$. Note that $y\in V(T_{1})$, as $\deg(y)\leq q+1$. If
$T_{2}=T_{1}-x$, then
${\mathcal{P}}^{\prime}=({\mathcal{P}}-\\{T_{1}\\})\cup\\{T_{2}\\}$ is a
partition of $T^{\prime}$ into induced trees of maximum degree at most $q+1$
obtained by Algorithm 1. By induction hypothesis ${\mathcal{P}}^{\prime}$ is a
smallest such partition. Since for any induced subtree $T^{*}$ of $T$ it holds
that $P_{q}(T^{*})\leq P_{q}(T)$, it follows that
$P_{q}(T)\leq|{\mathcal{P}}|=|{\mathcal{P}^{\prime}}|=P_{q}(T^{\prime})\leq
P_{q}(T)$, and thus $\mathcal{P}$ is a smallest partition of $T$ into induced
trees of maximum degree at most $q+1$.

Assume now that all support vertices of $T$ have degree at least $q+2$. Let
$y$ be a support vertex at maximum possible depth. Let $\mathcal{P}$ be the
partition of $T$ into induced trees of maximum degree $q+1$ obtained by
Algorithm 1. If $\deg_{T}(y)=q+2$, let $T^{\prime}$ be the tree obtained from
$T$ by deleting $y$ and all its leaf neighbors, i.e. $T^{\prime}=T-T_{y}$. If
all $q+2$ neighbors of $y$ are leaves, then $T$ is a star and the algorithm is
clearly correct. Otherwise, it follows from the algorithm that
$T_{y}\in\mathcal{P}$. Then ${\mathcal{P}}^{\prime}={\mathcal{P}}-\\{T_{y}\\}$
is the partition of $T^{\prime}$ into induced trees of maximum degree $q+1$
obtained by the algorithm. (Indeed in the first step of the algorithm
${\mathcal{P}}=\\{T_{y}\\}$ and $T=T-T_{y}$.) By the induction hypothesis
${\mathcal{P}}^{\prime}$ is a smallest such partition, i.e.
$P_{q}(T^{\prime})=|{\mathcal{P}}^{\prime}|$. Since
$P_{q}(T)=P_{q}(T^{\prime})+1$, $\mathcal{P}$ is a smallest such partition of
$T$.

Finally, let $\deg_{T}(y)=k+1>q+2$. Hence at least $k-q-1\geq 1$ leaf
neighbors of $y$ are singleton trees of $\mathcal{P}$. Let $x$ be one such
leaf and let $T^{\prime}=T-x$. Since
${\mathcal{P}}^{\prime}={\mathcal{P}}-\\{x\\}$ is a partition of $T^{\prime}$
into induced trees of maximum degree $q+1$ obtained by the algorithm,
${\mathcal{P}}^{\prime}$ is smallest such partition by the induction
hypothesis. Since $P_{q}(T)=P_{q}(T^{\prime})+1$ we deduce that
$|{\mathcal{P}}|=P_{q}(T)$, which completes the proof.

The algorithm is clearly implemented by first implementing BFS order and then
proceeding from bottom layers in direction to the root. In this way, the
vertices $x_{i}$ with $\deg(x_{i})>q+1$ are located exactly once and thus the
algorithm is clearly linear. $\square$

$x$ Figure 1: Graph $G$ with $F_{2}(G)<P_{2}(G)$.

In the article [2], the authors also showed that the inequality $F_{q}(G)\geq
P_{q}(G)$ holds for all graphs $G$ when $q=1$. However a similar result for
$q\geq 2$ is not true. Let $G$ be a graph as shown in Figure 1. Then
$F_{2}(G)=1$ with $\\{x\\}$ being an $F_{2}$-set, while $P_{2}(G)>1$, since
$G$ contains a vertex of degree $4$.

Next, we turn our attention to the bootstrap percolation number in trees;
moreover, our goal is to determine $\sigma_{(p,q)}$ when $p>1$. Riedl
described an algorithm for finding a smallest $p$-percolating set of a tree
$T$ in [22]. The algorithm works by reducing the tree $T$ into smaller
subtrees $T_{i}$ until every vertex is either a leaf or of an appropriate
degree. Then one can arbitrarily choose a $p$-percolating set of the subtree
$T_{i}$ by selecting all of its leaves. Notice that leaves always satisfy the
condition of a $(p,1)$ spreading set. When combining the percolating sets of
trees $T_{i}$ and $T_{j}$ to form the percolating set of a larger tree, we do
this by gluing the trees back together in a single vertex $v$. As it turns
out, $v$ always acts as a leaf, when proceeding with the infection process,
therefore this set also satisfies the condition of a $(p,1)$-spreading set.
All in all, the algorithm from [22] works also under the conditions of
$(p,1)$-spreading. We summarize this in the following result.

###### Theorem 4.3

If $p\geq 2$ and $T$ is a tree with maximum degree $\Delta$, then
$\sigma_{(p,q)}(T)=\sigma_{(p,1)}(T)$ for any
$q\in\mathbb{N}\cup\\{\infty\\}$. In particular,
$\sigma_{(p,\infty)}(T)=\sigma_{(p,\Delta)}(T)=\sigma_{(p,1)}(T)$.

Riedl [22] also proved that the algorithm runs in $O(n)$ time, which is thus
the complexity of determining $\sigma_{(p,q)}(T)$ for an arbitrary $p\geq 2$,
$q\in\mathbb{N}$, and an arbitrary tree $T$.

We conclude this subsection by compressing all of its theorems into the
following result.

###### Corollary 4.4

If $T$ is a tree, $p\in\mathbb{N}$ and $q\in\mathbb{N}\cup\\{\infty\\}$, then
${\sigma_{(p,q)}}(T)$ can be determined in linear time.

###  4.2 Bounds and extremal families

We start by observing that for every $q\in\mathbb{N}\cup\\{\infty\\}$, we have

${\sigma_{(p,q)}}(K_{1,n-1})=\begin{cases}n-1&\text{if }2\leq p\leq n-1\\\
n&\text{if }p\geq n.\end{cases}$

Next, we present a general upper bound on the $(p,q)$-spreading number of
trees, and determine the extremal trees.

###### Theorem 4.5

Let $T$ be a tree of order $n\geq 5$ and $q\in\mathbb{N}\cup\\{\infty\\}$.

  * i)

If $p=2$, then $\sigma_{(p,q)}(T)\leq n-1$ with equality if and only if
$T=K_{1,n-1}$;

  * ii)

If $p\geq 3$, then $\sigma_{(p,q)}(T)\leq n$ with equality if and only if
$\Delta(T)<p$.

Proof.  i) If $v$ is a vertex with $\deg(v)\geq 2$, then
$V(T)\setminus\\{v\\}$ is a $(p,q)$-spreading set of $T$. So, it is clear that
$\sigma_{(p,q)}(T)\leq n-1$. If $T=P_{n}$, then
$\sigma_{(p,q)}(P_{n})=\lceil(n+1)/2\rceil<n-1$ for $n\geq 5$. If $T\neq
P_{n}$ and $T\neq K_{1,n-1}$, then there exist vertices $u$ and $v$ with
$\deg(u)\geq 3$ and $\deg(v)\geq 2$. Now, $V(T)\setminus\\{u,v\\}$ is a
$(p,q)$-spreading set and hence $\sigma_{(p,q)}(T)\leq n-2$. ii) It is clear
that $\sigma_{(p,q)}(T)\leq n$, and by Remark 2.1(2), if $\Delta(T)<p$ then
$\sigma_{(p,q)}(T)=n$. Suppose that $\Delta(T)\geq p$ and let $v$ be a vertex
with $\deg(v)\geq p$. Now, $V(T)\setminus\\{v\\}$ is a $(p,q)$-spreading set
and hence $\sigma_{(p,q)}(T)\leq n-1$.

By the lower bound from [22] and noting that
$\sigma_{(p,1)}(T)={\sigma_{(p,q)}}(T)$ for any tree $T$ we immediately infer
the following.

###### Theorem 4.6

Let $T$ be a tree of order $n$ and $p\geq 2$. Then,

$\sigma_{(p,q)}(T)\geq\Big{\lceil}\frac{(p-1)}{p}n+\frac{1}{p}\Big{\rceil}.$

Let $\operatorname{rem}(N,p)$ denote the remainder when $N$ is divided by $p$
and let $f(n,p)=\lceil((p-1)n+1)/p\rceil$. We say that a tree $T$ of order $n$
satisfies property $\mathcal{P}(n,p)$ if $V=V(T)$ can be partitioned into two
subsets $S$ and $V\setminus S$ such that $|S|=f(n,p)$ and the vertices of
$V\setminus S$ can be ordered as $v_{1},\dots,v_{n-f(n,p)}$ and they satisfy
the following:

  * i)

$|N_{F_{i}}(v_{i})|\geq p$ for all $i$, and

  * ii)

$\operatorname{rem}(n-1,p)\geq\sum_{i=1}^{n-f(n,p)}\left(|N_{F_{i}}(v_{i})|-p\right)$,
and

  * iii)

There are exactly
$\operatorname{rem}(n-1,p)-\sum_{i=1}^{n-f(n,p)}\left(|N_{F_{i}}(v_{i})|-p\right)$
edges in the subgraph induced by $S$,

where each $F_{i}$ is a subforest of $T$ defined recursively by

$F_{1}=\\{v_{1}\\}\cup S_{1}\ \text{and}\ F_{i+1}=F_{i}\cup\\{v_{i+1}\\}\cup
S_{i+1}\ \text{for}\ 1\leq i\leq n-f(n,p)-1$

and $S_{i}=\\{u\in S\setminus\left(\bigcup\limits_{j<i}S_{j}\right):\
\text{there is a path in}\ T[S]\ \text{from}\ u\ \text{to a vertex in}\
N_{S}(v_{i})\\}$.

There are many trees satisfying the property $\mathcal{P}(n,p)$. As an
example, construct a tree $T^{*}$ as follows: let both
$S=\\{w_{1},\dots,w_{|S|}\\}$ and $V(T)\setminus
S=\\{v_{1},\dots,v_{n-|S|}\\}$ be independent sets with $|S|=f(n,p)$, and for
$1\leq i\leq n-|S|-1$, $N(v_{i})=\\{w_{1+(i-1)(p-1)},\dots,w_{1+i(p-1)}\\}$
and $N(v_{n-|S|})=\\{w_{1+(n-|S|-1)(p-1)},\dots,w_{|S|}\\}$, see Figure 2.
Observe that if $n-1$ is divisible by $p$, then $S$ is necessarily an
independent set.

$v_{1}$$v_{2}$$T^{*}$$v_{3}$

$v_{1}$$v_{2}$$v_{3}$$T^{\prime}$

Figure 2: Trees $T^{*}$ (left) and $T^{\prime}$ (right) with $n=11$ and $p=3$.

Next, we characterize all extremal trees in Theorem 4.6 via property
$\mathcal{P}(n,p)$. Given a spreading set $S$ of a graph $G$, we say that
$(v_{1},\dots,v_{n-|S|})$ is a $(p,q)$-spreading sequence if $V(G)\setminus
S=\\{v_{1},\dots,v_{n-|S|}\\}$ and there is a spreading process in which
vertices can become blue in the order of the sequence. Note that spreading
sequence is not necessarily unique. For example, in the tree $T^{*}$ in Figure
2, any ordering of vertices in $\\{v_{1},v_{2},v_{3}\\}$ is a spreading
sequence, and the tree $T^{\prime}$ has exactly three spreading sequences
which are $(v_{1},v_{2},v_{3})$, $(v_{1},v_{3},v_{2})$ and
$(v_{3},v_{1},v_{2})$.

###### Theorem 4.7

Let $T$ be a tree of order $n$ and $p\geq 2$. Then, $\sigma_{(p,q)}(T)=f(n,p)$
if and only if $T$ satisfies property $\mathcal{P}(n,p)$.

Proof.  First, suppose that $T$ satisfies property $\mathcal{P}(n,p)$. Then,
$(v_{1},\dots,v_{n-f(n,p)})$ is a $(p,q)$-spreading sequence of $T$ since
$|N_{F_{i}}(v_{i})|\geq p$ for all $i$. Thus, $S$ is a $(p,q)$-spreading set
of $T$ and $\sigma_{(p,q)}(T)\leq f(n,p)$. By Theorem 4.6, we have
$\sigma_{(p,q)}(T)\geq f(n,p)$. Hence, we obtain $\sigma_{(p,q)}(T)=f(n,p)$.

Now, let $S$ be a $(p,q)$-spreading set of $T$ and $(v_{1},\dots,v_{n-|S|})$
be a $(p,q)$-spreading sequence of $T$. At step $t$ of the spreading process,
all vertices in $F_{t}$ are blue and it is clear that $|N_{F_{i}}(v_{i})|\geq
p$ for all $i$, as $(v_{1},\dots,v_{n-|S|})$ is a $(p,q)$-spreading sequence
of $T$. Thus $i)$ holds. Let $k_{t}$ be the number of edges in the subgraph
induced by $S\cap V(F_{t})$ and $c_{t}$ be the number of connected components
of $F_{t}$. Now, we claim that for all $1\leq t\leq n-|S|$,

$|V(F_{t})|=k_{t}+c_{t}+\sum_{i=1}^{t}|N_{F_{i}}(v_{i})|.$ (1)

To prove (1), we proceed by induction on $t$. For $t=1$, we have
$|V(F_{1})|=1+|S_{1}|$, $k_{1}=|S_{1}|-|N_{S}(v_{1})|$, $c_{1}=1$ and
$|N_{F_{1}}(v_{1})|=|N_{S}(v_{1})|$. Hence, we obtain (1). Now suppose that
$t>1$. By the induction hypothesis,
$|V(F_{t-1})|=k_{t-1}+c_{t-1}+\sum_{i=1}^{t-1}|N_{F_{i}}(v_{i})|$. Since $T$
is a tree, the vertex $v_{t}$ has at most one neighbor in each component of
$F_{t-1}$. Moreover, $V(F_{t-1})\cap S_{t}=\emptyset$ and there is no edge
from vertices of $S_{t}$ to vertices of $V(F_{t-1})$ by the definition. Hence,
we obtain that $k_{t}=k_{t-1}+|S_{t}|-|N_{F_{t}}(v_{t})|+|V(F_{t-1})\cap
N_{F_{t}}(v_{t})|$ and $c_{t}=1+c_{t-1}-|V(F_{t-1})\cap N_{F_{t}}(v_{t})|$.

$\displaystyle|V(F_{t})|$ $\displaystyle=$ $\displaystyle
1+|S_{t}|+|V(F_{t-1})|$ $\displaystyle=$ $\displaystyle
1+|S_{t}|+k_{t-1}+c_{t-1}+\sum_{i=1}^{t-1}|N_{F_{i}}(v_{i})|$ $\displaystyle=$
$\displaystyle 1+c_{t-1}-|V(F_{t-1})\cap
N_{F_{t}}(v_{t})|+k_{t}+\sum_{i=1}^{t}|N_{F_{i}}(v_{i})|$ $\displaystyle=$
$\displaystyle c_{t}+k_{t}+\sum_{i=1}^{t}|N_{F_{i}}(v_{i})|$

For $t=n-|S|$, we have $F_{n-|S|}=T$ and therefore, $c_{n-|S|}=1$ and
$k_{n-|S|}=|E(G_{S})|$. So, (1) becomes

$n-1=p\,(n-|S|)+|E(T[S])|+\sum_{i=1}^{n-|S|}(|N_{F_{i}}(v_{i})|-p).$ (2)

It is easy to verify that $n-1=p\,(n-f(n,p))+\operatorname{rem}(n-1,p)$ for
all $n$ and $p$. Hence, if $|S|=f(n,p)$, then
$\operatorname{rem}(n-1,p)=|E(T[S])|+\sum_{i=1}^{n-|S|}(|N_{F_{i}}(v_{i})|-p)$.
Thus, every tree $T$ with a spreading set $S$ of size $f(n,p)$ satisfies (ii)
and (iii) in the definition of property $\mathcal{P}(n,p)$.

##  5 Spreading in grids

In this section, we determine the $(p,q)$-spreading number of grids for all
possible pairs $(p,q)$ with the exception when $p=3$. Let $G=P_{m}\square
P_{n}$, and without loss of generality let $n\leq m$.

Let $p=1$, that is consider the $q$-forcing problem in grids. If $q=1$, that
is, considering the zero forcing problem, it was proved in [2] that
$Z(G)=F_{1}(G)=\sigma_{(1,1)}(G)=n$. Clearly, we also have $F_{q}(G)=1$ for
$q\geq 2$.

The case when $p=3$ and $q\geq 4$, that is, ${\sigma_{(p,q)}}(G)=m(G,3)$, was
recently studied in [16, 23], but it seems that this is a difficult problem
for which only partial results are known. This is the only case of grids that
we will not resolve.

If $p>\Delta(G)=4$, Remark 2.1(2) implies that
${\sigma_{(p,q)}}(G)=|V(G)|=mn$. The case $p=4$ is resolved in the following
theorem.

###### Theorem 5.1

If $m,n\geq 3$ are positive integers, then
$\sigma_{(4,q)}(P_{m}\,\square\,P_{n})=2m+2n-4+\lfloor\frac{(m-2)(n-2)}{2}\rfloor$
for all $q\in\mathbb{N}$.

Proof.  Let $V(P_{m})=\\{1,2,\ldots,m\\}$ and $V(P_{n})=\\{1,2,\ldots,n\\}$
and let $S$ be a $(4,q)$-spreading set of $P_{m}\,\square\,P_{n}$. (Let us
call vertices $x\in P_{m}\,\square\,P_{n}$ with $\deg(x)<4$ boundary
vertices.) By Remark 2.1(1), all $2m+2n-4$ boundary vertices of $P_{m}\Box
P_{n}$ are contained in $S$. From the remaining $(m-2)\times(n-2)$ grid, we
claim that we must select vertices that form a vertex cover. Indeed, suppose
that there exists an edge $uv$ such that $u\notin S$ and $v\notin S$. Then in
any step of the color changing procedure, $u$ and $v$ each have at most three
blue neighbors, and thus $u$ and $v$ cannot be colored blue, and so $S$ is not
a $(4,q)$-spreading set, a contradiction. As the minimum vertex cover number
of the $(m-2)\times(n-2)$ grid is $\lfloor\frac{(m-2)(n-2)}{2}\rfloor$, we get
$|S|\geq 2m+2n-4+\lfloor\frac{(m-2)(n-2)}{2}\rfloor$. For the converse, one
can easily check that the boundary vertices of $P_{m}\Box P_{n}$ together with
the minimum vertex cover set of the remaining $(m-2)\times(n-2)$ grid forms a
$(4,q)$-spreading set and thus $\sigma_{(4,q)}(P_{m}\,\square\,P_{n})\leq
2m+2n-4+\lfloor\frac{(m-2)(n-2)}{2}\rfloor$. $\square$

1234512345678910 Figure 3: A minimum $(2,4)$-spreading set $S$ for
$G=P_{10}\,\square\,P_{5}$.

Next, we consider the case $p=2$. Let $G=P_{m}\square P_{n}$, and without loss
of generality, suppose that $n\leq m$. Bootstrap percolation was already
studied in grids by Bollobás, who proved that
$m(G,2)=\sigma_{(2,\infty)}(G)=\lceil\frac{n+m}{2}\rceil$ [6]. Since
$\Delta(G)=4$ it follows from Remark 2.1(3) that
$\sigma_{(2,q)}(G)=\sigma_{(2,\infty)}(G)=\lceil\frac{n+m}{2}\rceil$ for all
$q\geq 4$. In his solution Bollobás proposed a $(2,\infty)$-spreading set
(2-bootstrap percolating set) which consists of $n$ diagonal vertices on the
first $n$ columns and in the remaining columns $\lceil\frac{m-n}{2}\rceil$
vertices, one from every other column and one from the last column (see Figure
3). Notice that this set is also a $(2,3)$\- and a $(2,2)$-spreading set.
Therefore Remark 2.1(5) implies that
$\lceil\frac{n+m}{2}\rceil=\sigma_{(2,\infty)}(G)\leq\sigma_{(2,3)}(G)\leq\sigma_{(2,2)}(G)\leq\lceil\frac{n+m}{2}\rceil$.
Thus the only unsolved case for $p=2$ is the $(2,1)$-spreading number of $G$,
which we consider in the next result.

###### Theorem 5.2

If $m,n\geq 3$ are positive integers, then
$\sigma_{(2,1)}(P_{m}\,\square\,P_{n})=\lceil\frac{n+m+1}{2}\rceil$.

Proof.  First let $n+m$ be odd and without loss of generality let $m$ be even
and $n$ odd. Note that
$\lceil\frac{n+m+1}{2}\rceil=\lceil\frac{n+m}{2}\rceil$, therefore
$\lceil\frac{n+m}{2}\rceil=\sigma_{(2,\infty)}(G)\leq\sigma_{(2,1)}(G)$. Thus
it remains to find a $(2,1)$-spreading set of the same size. Consider the set
$S=\\{(1,1),(2,1),(4,1),\dots,(m,1),(1,3),(1,5),\dots,(1,n)\\}$ of size
$\frac{n+1}{2}+\frac{m}{2}=\lceil\frac{n+m}{2}\rceil$ (see Figure 4). It is
not hard to verify that $S$ is a $(2,1)$-spreading set of $G$. For instance,
by using the color change rule one can find the following sequence of color
changes:

$(1,2),(2,2),(3,1),(3,2),(2,3),(1,4),(2,4),(3,3),(4,2),(5,1),(5,2),\dots$

12345123456 Figure 4: A minimum $(2,1)$-spreading set $S$ for
$G=P_{6}\,\square\,P_{5}$.

Now let $n+m$ be even and let $S$ be an arbitrary $(2,1)$-spreading set.
Suppose $|S|\leq\frac{n+m}{2}$. Firstly, according to Lemma 2.2, set $S$ must
contain a pair of adjacent vertices. Now we use Bollobás’ idea of replacing
the grid with an uncolored chess board where each (unit) square corresponds to
a vertex in $G$. Color each square corresponding to a vertex of $S$ with blue,
others with white. Whenever a white square (adjacent to at least two blue
squares) is colored blue, the total perimeter of the blue domain (sum of
perimeters of blue polygons consisting of connected blue squares) does not
increase. Since the perimeter of the whole chess board (every vertex/square is
blue) is $2(n+m)$, the starting perimeter must also be at least $2(n+m)$.
Every blue square contributes at most 4 units to the total perimeter. Since we
know that at least 2 blue squares must be adjacent, their total perimeter can
be at most 6. The remaining $\frac{n+m}{2}-2$ blue squares contribute at most
$2(n+m)-8$, which means the total perimeter is at most $2(n+m)-2$, a
contradiction, hence $|S|\geq\frac{n+m}{2}+1$.

For the upper bound we consider two cases. If $n$ and $m$ are odd, let
$S=\\{(1,1),(2,1)$,
$(4,1),(6,1),\dots,(m-3,1),(m-1,1),(m,1),(1,3),(1,5),\dots,(1,n)\\}$. If $n$
and $m$ are even then let $S=\\{(1,1),(2,1),(4,1),(6,1)$,
$\dots,(m,1),(1,3),(1,5),\dots$, $(1,n-3),(1,n-1)(1,n)\\}$. In either case,
$S$ contains exactly $\frac{n+m}{2}+1$ vertices. One can easily check that a
similar pattern of blue color spreading as described in the case of $n+m$
being odd proves that $S$ is a $(2,1)$-spreading set. $\square$

All known results about the $(p,q)$-spreading number on $m\times n$ grids are
condensed in Table 2. Note that the values in the third row are still open,
while all other values of $\sigma_{(p,q)}(P_{m}\,\square\,P_{n})$ have been
established.

p q | $1$ | $2$ | $3$ | $4$ | $\geq 5$
---|---|---|---|---|---
1 | $n$ | $\mathbf{1}$
2 | $\mathbf{\bigl{\lceil}\frac{n+m+1}{2}\bigr{\rceil}}$ | $\bigl{\lceil}\frac{n+m}{2}\bigr{\rceil}$
3 |  |  |  | $\sigma_{(3,\infty)}$
4 | $\mathbf{2n+2m+\bigl{\lfloor}\frac{(m-2)(n-2)}{2}\bigr{\rfloor}}$
$\geq 5$ | $nm$
Table 2: $(p,q)$-spreading numbers of grids $P_{m}\Box P_{n}$. Values in bold
are results in this paper.

##  6 Concluding remarks

It follows from Remark 2.1 that
$\sigma_{(3,4)}(P_{m}\,\square\,P_{n})=\sigma_{(3,\infty)}(P_{m}\,\square\,P_{n})$
for any $m,n\geq 3$, since $\Delta(P_{m}\,\square\,P_{n})=4$. Unfortunately,
the exact values of the bootstrap percolation numbers
$m(P_{m}\,\square\,P_{n},3)$ ($=\sigma_{(3,\infty)}(P_{m}\,\square\,P_{n})$)
are not known in general; see [16, 23] for some known results and bounds, and
[12] for a related study. However, we believe that
$\sigma_{(3,3)}(P_{m}\,\square\,P_{n})=\sigma_{(3,4)}(P_{m}\,\square\,P_{n})=\sigma_{(3,\infty)}(P_{m}\,\square\,P_{n})$,
and pose this as a conjecture.

###### Conjecture 6.1

If $m,n\geq 3$, then
$\sigma_{(3,3)}(P_{m}\,\square\,P_{n})=\sigma_{(3,4)}(P_{m}\,\square\,P_{n})$.

Figure 5: Minimum $(3,3)$\- and $(3,1)$-spreading sets of
$P_{3}\,\square\,P_{3}$.

One might ask, if the conjecture is proven to be true, whether one can extend
the equality even further. While we did not find an answer to the question
whether $\sigma_{(3,2)}(G)=\sigma_{(3,3)}(G)$ is true for all grids $G$, we
can show that at least $\sigma_{(3,1)}(G)$ is not always equal to
$\sigma_{(3,3)}(G)$ if $G$ is a grid. See the example of
$G=P_{3}\,\square\,P_{3}$ in Figure 5, from which it is clear that
$\sigma_{(3,1)}(G)>\sigma_{(3,2)}(G)=\sigma_{(3,3)}(G)=\sigma_{(3,4)}(G)$,
therefore in general
$\sigma_{(3,1)}(P_{m}\,\square\,P_{n})\neq\sigma_{(3,3)}(P_{m}\,\square\,P_{n})$.

Even if one can prove Conjecture 6.1, this does not necessarily mean that one
can determine $\sigma_{(3,3)}(P_{m}\,\square\,P_{n})$ or
$\sigma_{(3,4)}(P_{m}\,\square\,P_{n})$. Based on some earlier partial
results, this could be a hard problem, which we pose next.

###### Problem 1

Determine $\sigma_{(3,q)}(P_{m}\Box P_{n})$, where $q\leq 4$, for all positive
integers $m$ and $n$.

Obtaining upper and lower bounds on $\sigma_{(3,q)}(P_{m}\Box P_{n})$ would be
a natural way to approach Problem 1. Alternatively, one could aim to obtain
exact values while fixing one of the integers $m$ or $n$; we again refer to
[16, 23] for known values.

Hypercubes, alias $n$-cubes, are one of the most important graph classes with
numerous applications; one can define the $n$-cube, $Q_{n}$, as
$K_{2}\,\square\,\cdots\,\square\,K_{2}$, where there are $n$ factors. In
particular, it is known that $\sigma_{(1,1)}(Q_{n})=2^{n-1}$ [2]. In addition,
$\sigma_{(2,\infty)}(Q_{n})=\lceil\frac{n}{2}\rceil+1$, as proved in [4], and
$\sigma_{(3,\infty)}(Q_{n})=\lceil\frac{n(n+3)}{6}\rceil+1$, as proved in
[21]. A natural problem is to determine the $(p,q)$-spreading numbers of
$n$-cubes for other values of $p$ and $q$.

###### Problem 2

Determine $\sigma_{(p,q)}(Q_{n})$, where $Q_{n}$ is the $n$-cube of dimension
$n$ for all $p\in\mathbb{N},q\in\mathbb{N}\cup\\{\infty\\}$.

The most natural generalizations of hypercubes are Hamming graphs, which are
the Cartesian products of several complete graphs. Problem 2 could thus be
extended to determining $\sigma_{(p,q)}(K_{r_{1}}\Box\cdots\Box K_{r_{n}})$,
where $K_{r_{i}}$ are complete graphs. This problem was considered for
$P_{3}$-convexity in [8], where it was proved that
$\sigma_{(2,\infty)}(K_{r_{1}}\Box\cdots\Box K_{r_{n}})=\lceil n/2\rceil+1$.

## Acknowledgement

B.B. was supported by the Slovenian Research Agency (ARRS) under the grants
P1-0297, J1-2452, J1-3002, and J1-4008. T.D. was supported by the Slovenian
Research Agency (ARRS) under the grants P1-0297 and J1-2452. J.H. was
supported by the Slovenian Research Agency (ARRS) under the grants P1-0297.

## References

  * [1] A. Aazami, Hardness results and approximation algorithms for some problems on graphs, ProQuest LLC, Ann Arbor, MI, 2009, Thesis (Ph.D.), University of Waterloo (Canada).
  * [2] AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear algebra Appl. 428 (2008) 1628–1648.
  * [3] D. Amos, Y. Caro, R. Davila, R. Pepper, Upper bounds on the k-forcing number of a graph, Discrete Appl. Math. 181 (2015) 1–10.
  * [4] J. Balogh, B. Bollobás, Bootstrap percolation on the hypercube, Probab. Theory Related Fields 134 (2006) 624–648.
  * [5] J. Balogh, G. Pete, Random disease on the square grid, Random Str. Alg. 13 (1998) 409–422.
  * [6] B. Bollobás, The Art of Mathematics: Coffee Time in Memphis. Cambridge Univ. Press, New York, 2006.
  * [7] B. Brešar, Cs. Bujtás, T. Gologranc,, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza, M. Vizer, Grundy dominating sequences and zero forcing sets. Discrete Opt. 26 (2017) 66–77.
  * [8] B. Brešar, M. Valencia-Pabon, On the $P_{3}$-hull number of Hamming graphs, Discrete Appl. Math. 282 (2020) 48–52.
  * [9] D. Burgarth, V. Giovannetti, Full control by locally induced relaxation, Phys. rev. lett. 99 (2007) 100501.
  * [10] C.C. Centeno, L.D. Penso, D. Rautenbach, V.G.P. de Sá, Geodetic number versus hull number in $P_{3}$-convexity, SIAM J. Discrete Math. 27 (2013) 717–731.
  * [11] J. Chalupa, P.L. Leath, G.R. Reich, Bootstrap percolation on a Bethe lattice, J. Physics C: Solid State Physics 12 (1979) L31.
  * [12] P.J. Dukes, J.A. Noel, and A.E. Romer, Extremal bounds for three-neighbour bootstrap percolation in dimensions two and three, arXiv:2209.07594 19 Sep 2022.
  * [13] S.M. Fallat, L. Hogben, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl. 426 (2007) 558–582.
  * [14] M. Gentner, Michael, L. Penso, D. Rautenbach, U. Souza, Extremal values and bounds for the zero forcing number, Discrete Appl. Math. 214 (2016) 196–200.
  * [15] D. Ferrero, L. Hogben, F. Kenter, M. Young, The relationship between $k$-forcing and $k$-power domination, Discrete Math. 341 (2018) 1789–1797.
  * [16] J. Hedžet, M. Henning, $3$-Neighbor bootstrap percolation on grids, arXiv:2307.14033.
  * [17] L. Hogben, J. C.-H. Lin, B.L. Shader, Inverse problems and zero forcing for graphs, Mathematical Surveys and Monographs 270, American Mathematical Society, Providence, 2022.
  * [18] T. Kalinowski, N. Kamčev and B. Sudakov. The zero forcing number of graphs, SIAM J. Discrete Math. 33 (2019) 95–115.
  * [19] J.C.-H. Lin, Zero forcing number, Grundy domination number, and their variants, Linear Algebra Appl. 563 (2019) 240–254.
  * [20] Z. Montazeri, N. Soltankhah, Nasrin, $k$-forcing number for the Cartesian product of some graphs, Contrib. Discrete Math. 16 (2021) 89–97.
  * [21] N. Morrison, J.A. Noel, Extremal bounds for bootstrap percolation in the hypercube, J. Combin. Theory Ser. A 156 (2018) 61–84.
  * [22] E. Riedl, Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012) Paper 64 (18 pp).
  * [23] A.E. Romer. Tight bounds on $3$-neighbor bootstrap percolation. Master’s thesis, University of Victoria, Victoria, Canada, 2022.