Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

6-6-2017

Journal or Book Title

arxiv

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) = 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. .]

Comments

This is a manuscript made available through arxiv: https://arxiv.org/abs/1610.04499.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS