PreprintCC0arXiv
2-Neighbor Bootstrap Percolation on Odd Graphs
Abstract
The r-neighbor bootstrap percolation process on a graph G is a vertex-activation process that begins with a set of initially active vertices. In each subsequent round, every inactive vertex having at least r active neighbors becomes active. Denote by m(G,r) the minimum number of initially active vertices whose activation eventually spreads to all vertices of G. Let mathbbmslOk and mathbbmslBk be the odd graph and the bipartite odd graph, respectively, both defined on a ground set of size 2k+1. In this article, among other results, we prove that m(mathbbmslOk, 2)=⌈(k2+3k+2)/4⌉ and m(mathbbmslBk, 2)=⌈(k2+2k+3)/2⌉. The former result confirms a conjecture posed in 2021 by Grippo, Pastine, Torres, Valencia-Pabon, and Vera.
Related
- Minimum Weakly Saturated Graphs and Bootstrap Percolation in General Host Graphs
- Two-neighbor lattice percolation percolates in all dimensions
- Stretched exponential asymptotics for bases of triangular bootstrap percolation
- Bootstrap percolation on the hypercube
- Seed thresholds and degree variance in heterogeneous bootstrap percolation with growing degrees
BibTeX
@misc{mohammadian20262neighbor,
title = {{$\boldsymbol2$-Neighbor Bootstrap Percolation on Odd Graphs}},
author = {Ali Mohammadian and Sina Rezaie Zareie and Behruz Tayfeh-Rezaie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.03687},
eprint = {2606.03687},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.03687},
note = {CC0},
}
RIS
TY - UNPB
TI - 2-Neighbor Bootstrap Percolation on Odd Graphs
AU - Ali Mohammadian
AU - Sina Rezaie Zareie
AU - Behruz Tayfeh-Rezaie
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2606.03687
UR - https://arxiv.org/abs/2606.03687
AB - The r-neighbor bootstrap percolation process on a graph G is a vertex-activation process that begins with a set of initially active vertices. In each subsequent round, every inactive vertex having at least r active neighbors becomes active. Denote by m(G,r) the minimum number of initially active vertices whose activation eventually spreads to all vertices of G. Let mathbbmslO_k and mathbbmslB_k be the odd graph and the bipartite odd graph, respectively, both defined on a ground set of size 2k+1. In this article, among other results, we prove that m(mathbbmslO_k, 2)=⌈(k^2+3k+2)/4⌉ and m(mathbbmslB_k, 2)=⌈(k^2+2k+3)/2⌉. The former result confirms a conjecture posed in 2021 by Grippo, Pastine, Torres, Valencia-Pabon, and Vera.
ER -