Article in press
Authors:
Jaka Hedžet
Institute of Mathematics, Physics and Mechanics
University of Ljubljana, Slovenia
email: jaka.hedzet@imfm.com
Title:
3-Neighbor bootstrap percolation on grids
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-06-10 , Revised: 2023-11-04 , Accepted: 2023-11-06 , Available online: 2023-11-29 , https://doi.org/10.7151/dmgt.2531
Abstract:
Given a graph $G$ and assuming that some vertices of $G$ are infected, the
$r$-neighbor bootstrap percolation rule makes an uninfected vertex $v$ infected
if $v$ has at least $r$ infected neighbors. The $r$-percolation number,
$m(G, r)$, of $G$ is the minimum cardinality of a set of initially infected
vertices in $G$ such that after continuously performing the $r$-neighbor
bootstrap percolation rule each vertex of $G$ eventually becomes infected. In
this paper, we consider the $3$-bootstrap percolation number of grids with
fixed widths. If $G$ is the Cartesian product $P_3 \mathbin{\Box} P_m$ of two paths of
orders $3$ and $m$, we prove that $m(G,3)=\frac{3}{2}(m+1)-1$, when $m$ is odd,
and $m(G,3)=\frac{3}{2}m +1$, when $m$ is even. Moreover, if $G$ is the Cartesian
product $P_5 \mathbin{\Box} P_m$, we prove that $m(G,3)=2m+2$, when $m$ is odd, and
$m(G,3)=2m+3$, when $m$ is even. If $G$ is the Cartesian product $P_4 \mathbin{\Box} P_m$,
we prove that $m(G,3)$ takes on one of two possible values, namely
$m(G,3) = \left\lfloor \frac{5(m+1)}{3} \right\rfloor + 1$ or $m(G,3) = \left
\lfloor\frac{5(m+1)}{3} \right\rfloor + 2$.
Keywords:
bootstrap percolation, $3$-percolation number, grids
References:
- J. Balogh and B. Bollobás, Bootstrap percolation on the hypercube, Probab. Theory Related Fields 134 (2006) 624–648.
https://doi.org/10.1007/s00440-005-0451-6 - J. Balogh, B. Bollobás, H. Duminil-Copin and R. Morris, The sharp threshold for bootstrap percolation in all dimensions, Trans. Amer. Math. Soc. 364 (2012) 2667–2701.
https://doi.org/10.1090/S0002-9947-2011-05552-2 - J. Balogh and G. Pete, Random disease on the square grid, Random Structures Algorithms 13 (1998) 409–422.
https://doi.org/10.1002/(SICI)1098-2418(199810/12)13:3/4<409::AID-RSA11>3.3.CO;2-5 - F. Benevides, J.C. Bermond, H. Lesfari and N. Nisse, Minimum Lethal Sets in Grids and Tori under $3$-Neighbour Bootstrap Percolation, PhD Thesis (Université Côte d'Azur, 2021).
- F. Benevides and M. Przykucki, Maximum percolation time in two-dimensional bootstrap percolation, SIAM J. Discrete Math. 29 (2015) 224–251.
https://doi.org/10.1137/130941584 - M. Bidgoli, A. Mohammadianm and B. Tayfeh-Rezaie, Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs, European J. Combin. 92 (2021) 103256.
https://doi.org/10.1016/j.ejc.2020.103256 - B. Bollobás, The Art of Mathematics: Coffee Time in Memphis (Cambridge University Press, 2006).
https://doi.org/10.1017/CBO9780511816574 - B. Brešar and M. Valencia-Pabon, On the $P_3$-hull number of Hamming graphs, Discrete Appl. Math. 282 (2020) 48–52.
https://doi.org/10.1016/j.dam.2019.11.011 - C.C. Centeno, S. Dantas, M.C. Dourado, D. Rautenbach and J.L. Szwarcfiter, Convex partitions of graphs induced by paths of order three, Discrete Math. Theor. Comput. Sci. 12 (2010) 175–184.
https://doi.org/10.46298/dmtcs.502 - C.C. Centeno, L.D. Penso, D. Rautenbach and V.G. Pereira de Sá, Geodetic number versus hull number in $P_3$-convexity, SIAM J. Discrete Math. 27 (2013) 717–731.
https://doi.org/10.1137/110859014 - J. Chalupa, P.L. Leath and G.R. Reich, Bootstrap percolation on a Bethe lattice, J. Phys. C 12 (1979) 31–35.
https://doi.org/10.1088/0022-3719/12/1/008 - E.M.M. Coelho, H. Coelho, J.R. Nascimento and J.L. Szwarcfiter, On the $P_3$-hull number of some products of graphs, Discrete Appl. Math. 253 (2019) 2–13.
https://doi.org/10.1016/j.dam.2018.04.024 - E.M.M. Coelho, M.C. Dourado and R.M. Sampaio, Inapproximability results for graph convexity parameters, Theoret. Comput. Sci. 600 (2015) 49–58.
https://doi.org/10.1016/j.tcs.2015.06.059 - M. Dairyko, M. Ferrara, B. Lidický, R.R. Martin, F. Pfender and A.J. Uzzell, Ore and Chvátal-type degree conditions for bootstrap percolation from small sets, J. Graph Theory 94 (2020) 252–266.
https://doi.org/10.1002/jgt.22517 - P. Dukes, J. Noel and A. Romer, Extremal bounds for $3$-neighbor bootstrap percolation in dimensions two and three, SIAM J. Discrete Math. 37 (2023) 2088–2125.
https://doi.org/10.1137/22M1534195 - L.N. Grippo, A. Pastine, P. Torres, M. Valencia-Pabon and J.C. Vera, On the $P_3$-hull number of Kneser graphs, Electron. J. Combin. 28(3) (2021) #P3.32.
https://doi.org/10.37236/9903 - K. Gunderson, Minimum degree conditions for small percolating sets in bootstrap percolation, Electron. J. Combin. 27(2) (2020) #P2.37.
https://doi.org/10.37236/6937 - R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs (CRC Press, Boca Raton, FL, 2011).
- T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Structures of Domination in Graphs, Dev. Math. 66 (Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5 - M.A. Henning and A. Yeo, Total Domination in Graphs, Springer Monogr. Math. (Springer, New York, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - T. Marcilon and R. Sampaio, The maximum time of $2$-neighbor bootstrap percolation: Complexity results, Theoret. Comput. Sci. 708 (2018) 1–17.
https://doi.org/10.1016/j.tcs.2017.10.014 - R. Morris, Minimal percolating sets in bootstrap percolation, Electron.\ J.\ Combin. 16(1) (2009) #R2.
https://doi.org/10.37236/91 - M. Przykucki and T. Shelton, Smallest percolating sets in bootstrap percolation on grids, Electron. J. Combin. 27(4) (2020) #P4.34.
https://doi.org/10.37236/9582 - M. Przykucki, Maximal percolation time in hypercubes under $2$-bootstrap percolation, Electron. J. Combin. 19(2) (2012) #P41.
https://doi.org/10.37236/2412 - A.E. Romer, Tight Bounds on $3$-Neighbor Bootstrap Percolation, Master's Thesis (University of Victoria, Victoria, Canada, 2022).
Close