Campus Units


Document Type


Publication Version

Submitted Manuscript

Publication Date


Journal or Book Title



Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph G begin in one of two states, “dormant” or “active”. Given a fixed positive integer r, a dormant vertex becomes active if at any stage it has at least r active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices A, we say that G r- percolates (from A) if every vertex in G becomes active after some number of steps. Let m(G, r) denote the minimum size of a set A such that G r-percolates from A.

Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure m(G, 2) = 2. In particular, we give an Ore-type degree sum result that states that if a graph G satisfies σ2(G) ≥ n − 2, then either m(G, 2) = 2 or G is in one of a small number of classes of exceptional graphs. (Here, σ2(G) = min{d(x)+ d(y) : xy ∈/ E(G)}.) We also give a Chvátal-type degree condition: If G is a graph with degree sequence d1 ≤ d2 ≤ · · · ≤ dn such that di ≥ i + 1 or dn−i ≥ n − i − 1 for all 1 ≤ i < n , then m(G, 2) = 2 or G falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. .]


This is a manuscript made available through arxiv:

Copyright Owner

The Authors



File Format