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.