Bootstrap percolation in Ore-type graphs

MaRDI QIDQ6325040zbMATH OpenFDO

Authors Alexandra Wesolek

Publication date 10 September 2019

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Abstract: The $r$-neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as soon as it has $r$ infected neighbours. An inital set of infected vertices is called percolating if at the end of the bootstrap process all vertices are infected. We give Ore-type conditions that guarantee the existence of a small percolating set of size $lleq2r-2$ if the number of vertices $n$ of our graph is sufficiently large: if $lgeqr$ and satisfies $2rgeql+2lfloorsqrt2(l-r)+0.25+2.5floor-1$ then there exists a percolating set of size $l$ for every graph in which any two non-adjacent vertices $x$ and $y$ satisfy $deg(x)+deg(y)geqn+4r-2l-2lfloorsqrt2(l-r)+0.25+2.5floor-1$ and if $l$ is larger with $lleq2r-2$ there exists a percolating set of size $l$ if $deg(x)+deg(y)geqn+2r-l-2$. Our results extend the work of Gunderson, who showed that a graph with minimum degree $lfloorn/2floor+r-3$ has a percolating set of size $rgeq4$. We also give bounds for arbitrarily large $l$ in the minimum degree setting.

This page was built for publication: Bootstrap percolation in Ore-type graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325040)