Article in press
Authors:
Title:
Bootstrap percolation and $P_3$-hull number in direct products of graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-03-10 , Revised: 2025-08-09 , Accepted: 2025-08-11 , Available online: 2025-09-15 , https://doi.org/10.7151/dmgt.2603
Abstract:
The $r$-neighbor bootstrap percolation is a graph infection process based on
the update rule by which a vertex with $r$ infected neighbors becomes infected.
We say that an initial set of infected vertices propagates if all vertices of a
graph $G$ are eventually infected, and the minimum cardinality of such a set in
$G$ is called the $r$-bootstrap percolation number, $m(G,r)$, of $G$. In this
paper, we study percolating sets in direct products of graphs. While in general
graphs there is no non-trivial upper bound on $m(G× H,r)$, we prove several
upper bounds under the assumption $\delta(G)\ge r$.
We also characterize the connected graphs $G$ and $H$ with minimum degree $2$
that satisfy $m(G × H, 2)=\frac{|V(G × H)|}{2}$. In addition, we
determine the exact values of $m(P_n × P_m, 2)$, which are $m+n-1$ if $m$
and $n$ are of different parities, and $m+n$ otherwise.
Keywords:
bootstrap percolation, direct product of graphs, $P_3$-convexity
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.0.CO;2-U - M. Bidgoli, A. Mohammadian 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 J. Hedžet, Bootstrap percolation in strong products of graphs, Electron. J. Combin. 31 (2024) #P4.35.
https://doi.org/10.37236/11826 - 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 - V. Campos, R.M. Sampaio, A. Silva and J.L. Szwarcfiter, Graphs with few $P_4$'s under the convexity of paths of order three, Discrete Appl. Math. 192 (2015) 28–39.
https://doi.org/10.1016/j.dam.2014.05.005 - M.R. Cappelle, E.M.M. Coelho, H. Coelho, B.R. Silva, F. Protti and U.S. Souza, $P_3$-hull number of graphs with diameter two, Electron. Notes Theor. Comput. Sci. 346 (2019) 309–320.
https://doi.org/10.1016/j.entcs.2019.08.028 - 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(5) (2010) 175–184.
https://doi.org/10.46298/dmtcs.502 - 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 - L.M. González, L.N. Grippo and M.D. Safe, Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs, Australas. J. Combin. 79 (2021) 401–423.
- 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 (2021) #P3.32.
https://doi.org/10.37236/9903 - R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, 2011).
https://doi.org/10.1201/b10959 - M. Morrison and J.A. Noel, Extremal bounds for bootstrap percolation in the hypercube, J. Combin. Theory Ser. A 156 (2018) 61–84.
https://doi.org/10.1016/j.jcta.2017.11.018 - M. Przykucki and T. Shelton, Smallest percolating sets in bootstrap percolation on grids, Electron. J. Combin. 27 (2020) #P4.34.
https://doi.org/10.37236/9582 - Y. Shitov, Counterexamples to Hedetniemi's conjecture, Ann. of Math. 190 (2019) 663–667.
https://doi.org/10.4007/annals.2019.190.2.6 - C. Tardif, Hedetniemi's conjecture, $40$ years later, Graph Theory Notes N. Y. 54 (2008) 46–57.
- D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, USA, 2001).
- X. Zhu, A survey of Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998) 1–24.
https://doi.org/10.11650/twjm/1500406890
Close