Ore and Chvátal‐type degree conditions for bootstrap percolation from small sets. Issue 2 (8th November 2019)

• Record Type: Journal Article
• Authors: Dairyko, Michael; Ferrara, Michael; Lidický, Bernard; Martin, Ryan R.; Pfender, Florian; Uzzell, Andrew J.
• Is Part Of: Journal of graph theory. Volume 94:Issue 2(2020)
• Page Start: 252
• Page End: 266
• Publication Date: 2019-11-08
• Subjects: bootstrap percolation -- chvàtal condition -- ore condition; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22517
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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 ) is the minimum sum of degrees of two nonadjacent vertices in G .) We also give a Chvátal‐type degree condition: If G is a graph with degree sequence d 1 ≤ d 2 ≤ ⋯ ≤ d n such that d i ≥ i + 1 or d n − i ≥ n − i − 1 for all 1 ≤ i < n 2, 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 a paper by Freund et al.