3-NEIGHBOR BOOTSTRAP PERCOLATION ON GRIDS

Given a graph G and assuming that some vertices of G are infected, the r-neighbor bootstrap percolation rule makes an uninfected vertex v infected if v has at least r infected neighbors. The r-percolation number, m(G, r), of G is the minimum cardinality of a set of initially infected vertices in G such that after continuously performing the r-neighbor bootstrap percolation rule each vertex of G eventually becomes infected. In this paper, we consider the 3-bootstrap percolation number of grids with fixed widths. If G is the Cartesian product P3 □ Pm of two paths of orders 3 and m, we prove that m(G, 3) = 3 2 (m + 1) - 1, when m is odd, and m(G, 3) = 3 2m + 1, when m is even. Moreover, if G is the Cartesian product P5 □ Pm, we prove that m(G, 3) = 2m + 2, when m is odd, and m(G, 3) = 2m + 3, when m is even. If G is the Cartesian product P4 □ Pm, we prove that m(G, 3) takes on one of two possible values, namely m(G, 3) = ⌊ 5(m+1) 3 ⌋ + 1 or m(G, 3) = ⌊ 5(m+1) 3 ⌋ + 2.(Formula