Bootstrap percolation and P₃-hull number in direct products of graphs

The r-neighbor bootstrap percolation is a graph infection process based on the update rule by which a vertex with r infected neighbors becomes infected. We say that an initial set of infected vertices propagates if all vertices of a graph G are eventually infected, and the minimum cardinality of such a set in G is called the r-bootstrap percolation number, $m(G,r)$, of G. In this paper, we study percolating sets in direct products of graphs. While in general graphs there is no non-trivial upper bound on m(G× H,r), we prove several upper bounds under the assumption δ(G)≥ r. We also characterize the connected graphs G and H with minimum degree $2$ that satisfy m(G × H, 2) = |V(G × H)|/2. In addition, we determine the exact values of m(Pₙ × Pₘ, 2), which are $m+n-1$ if m and n are of different parities, and $m+n$ otherwise.