$3$-Neighbor bootstrap percolation on grids

Abstract

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 $P_3\square P_m$ of two paths of orders~$3$ and $m$, we prove that $m(G,3)=\frac{3}{2}(m+1)-1$, when $m$ is odd, and $m(G,3)=\frac{3}{2}m+1$, when $m$ is even. Moreover if $G$ is the cartesian product $P_5\square P_m$, 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 $P_4\square P_m$, we prove that $m(G,3)$ takes on one of two possible values, namely $m(G,3)=\lfloor \frac{5(m+1)}{3}\rfloor +1$ or $m(G,3)=\lfloor \frac{5(m+1)}{3}\rfloor +2$.

27 pages, 13 figures