The r-neighbour bootstrap process is an update rule for the states of vertices in which 'uninfected' vertices with at least r 'infected' neighbours become infected and a set of initially infected vertices is said to percolate if eventually all vertices are infected. For every r >= 3, a sharp condition is given for the minimum degree of a sufficiently large graph that guarantees the existence of a percolating set of size r. In the case r = 3, for n large enough, any graph on n vertices with minimum degree [n/2] + 1 has a percolating set of size 3 and for r >= 4 and n large enough (in terms of r), every graph on n vertices with minimum degree [n/2] + (r - 3) has a percolating set of size r. A class of examples are given to show the sharpness of these results.
展开▼
