arXiv Analytics

Sign in

arXiv:1909.04649 [math.CO]AbstractReferencesReviewsResources

Bootstrap percolation in Ore-type graphs

Alexandra Wesolek

Published 2019-09-10Version 1

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 $l\leq 2r-2$ if the number of vertices $n$ of our graph is sufficiently large: if $l\geq r$ and satisfies $2r \geq l+2 \lfloor \sqrt{2(l-r)+0.25}+2.5 \rfloor-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) \geq n+4r-2l-2\lfloor\sqrt{2(l-r)+0.25}+2.5 \rfloor-1$ and if $l$ is larger with $l\leq 2r-2$ there exists a percolating set of size $l$ if $deg(x)+deg(y) \geq n+2r-l-2$. Our results extend the work of Gunderson, who showed that a graph with minimum degree $\lfloor n/2 \rfloor+r-3$ has a percolating set of size $r \geq 4$. We also give bounds for arbitrarily large $l$ in the minimum degree setting.

Comments: 26 pages, 5 figures
Categories: math.CO
Subjects: 05C35, 05C99, G.2.2
Related articles: Most relevant | Search more
arXiv:1506.04686 [math.CO] (Published 2015-06-15)
Extremal Bounds for Bootstrap Percolation in the Hypercube
arXiv:1610.04499 [math.CO] (Published 2016-10-14)
Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets
arXiv:math/0212373 [math.CO] (Published 2002-12-30)
The order of monochromatic subgraphs with a given minimum degree