2023/07/26 by Jaka Hedžet, Hedžet, Jaka, Michael A. Henning +1 · 1 citation
Mathematics · #05C38 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2307.14033
openalex publication_date 2023/07/26 · openalex created_date 2023/07/28 · openalex updated_date 2026/07/28
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 \square 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)/(2)m +1, when m is even. Moreover if G is the cartesian product P5 \square 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 \square Pm, we prove that m(G,3) takes on one of two possible values, namely m(G,3) = \lfloor (5(m+1))/(3) \rfloor + 1 or m(G,3) = \lfloor (5(m+1))/(3) \rfloor + 2.