Largest and smallest minimal percolating sets in trees (Q426841)

Summary: Originally introduced by \textit{J. Chalupa}, \textit{P.L. Leath} and \textit{G.R. Reich} [``Bootstrap percolation on a Bethe lattice'', J. Phys. C., 12, L31--L35, (1979)] 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.