Largest and smallest minimal percolating sets in trees

Eric Riedl¹

¹Harvard University

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

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.

Détail

DOI : 10.37236/2152

Classification : 05C05, 05C12, 05C85
Mots-clés : percolation, graph theory