Largest and Smallest Minimal Percolating Sets in Trees

Abstract

Originally introduced by Chalupa, Leath and Reich for use in modeling disordered magnetic systems, $r$-bootstrap percolation is the following deterministic process on a graph.  Given an initial infected set, vertices with at least $r$ infected neighbors are infected until no new vertices can be infected.  A set percolates if it infects all the vertices of the graph, and a percolating set is minimal if no proper subset percolates.  We consider minimal percolating sets in finite trees.  We show that if $A$ is a minimal percolating set on a tree $T$ with $n$ vertices and $\ell$ vertices of degree less than $r$ (leaves in the case $r=2$), then $\frac{(r-1)n+1}{r} \leq |A| \leq \frac{rn+\ell}{r+1}$.  Moreover, we show that the difference between the sizes of a largest and smallest minimal percolating sets is at most $\frac{(r-1)(n-1)}{r^2}$.  Finally, we describe $O(n)$ algorithms for computing the largest (for $r=2$) and smallest (for $r \geq 2$) minimal percolating sets.