Largest Minimal Percolating Sets in Hypercubes under $2$-Bootstrap Percolation

Consider the following process, known as $r$-bootstrap percolation, on a graph $G$. Designate some initial infected set $A$ and infect any vertex with at least $r$ infected neighbors, continuing until no new vertices can be infected. We say $A$ percolates if it eventually infects the entire graph. W...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2010-05, Vol.17 (1)
Main Author: Riedl, Eric
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider the following process, known as $r$-bootstrap percolation, on a graph $G$. Designate some initial infected set $A$ and infect any vertex with at least $r$ infected neighbors, continuing until no new vertices can be infected. We say $A$ percolates if it eventually infects the entire graph. We say $A$ is a minimal percolating set if $A$ percolates, but no proper subset percolates. We compute the size of a largest minimal percolating set for $r=2$ in the $n$-dimensional hypercube.
ISSN:1077-8926
1077-8926
DOI:10.37236/352