Premium
Contagious sets in a degree‐proportional bootstrap percolation process
Author(s) -
Garbe Frederik,
Mycroft Richard,
McDowell Andrew
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20818
Subject(s) - combinatorics , mathematics , vertex (graph theory) , upper and lower bounds , connectivity , graph , vertex connectivity , discrete mathematics , mathematical analysis
We study the following bootstrap percolation process: given a connected graph G , a constant ρ ∈ [0,1] and an initial set A ⊆ V ( G ) of infected vertices, at each step a vertex v becomes infected if at least a ρ ‐proportion of its neighbors are already infected (once infected, a vertex remains infected forever). Our focus is on the size h ρ ( G ) of a smallest initial set which is contagious , meaning that this process results in the infection of every vertex of G . Our main result states that every connected graph G on n vertices has h ρ ( G ) < 2 ρn or h ρ ( G ) = 1 (note that allowing the latter possibility is necessary because of the case ρ ≤ 1 2 n , as every contagious set has size at least one). This is the best‐possible bound of this form, and improves on previous results of Chang and Lyuu and of Gentner and Rautenbach. We also provide a stronger bound for graphs of girth at least five and sufficiently small ρ , which is asymptotically best‐possible.