A journey through virality

Let η ≥ 1 be any non negative integer and let G = (V, E) be any undirected graph in which a subset D ⊆ V of vertices are initially infected. We consider the following process in which, at every step, each non-infected vertex with at least η infected neighbours becomes infected. The problem consists in determining the minimum size s η (G) of an initially infected vertices set D that eventually infects the whole graph G. Note that s 1 (G) = 1 for any connected graph G. This problem is closely related to cellular automata, to percolation problems and to the Game of Life studied by John Conway. The case when G is the n × n grid G n×n and η = 2 is well known and appears in many puzzles books, in particular due to the elegant proof that shows that s 2 (G n×n) = n for all n ∈ N. We study the cases of square grids G n×n and tori T n×n when η ∈ {3, 4}. We show that s 3 (G n×n) = n 2 +2n+4 3 for every n even and that n 2 +2n 3 ≤ s 3 (G n×n) ≤ n 2 +2n 3 + 1 for any n odd. When n is odd, we show that both bounds are reached, namely s 3 (G n×n) = n 2 +2n 3 if n ≡ 5 (mod 6) or n = 2 p − 1 for any p ∈ N * , and s 3 (G n×n) = n 2 +2n 3 + 1 if n ∈ {9, 13}. Finally, for all n ∈ N, we give the exact expression of s 4 (G n×n) and of s η (T n×n) when η ∈ {3, 4}.