Spreading in claw-free cubic graphs

• Autorzy: Brešar Boštjan , Hedžet Jaka , Henning Michael A.

Identyfikatory

DOI

10.7494/OpMath.2025.45.5.581

• Języki publikacji: EN

Abstrakty

EN

Let p ∈ N and q ∈ N ∪ {∞}. We study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of blue vertices, with all remaining vertices colored white. If a white vertex v has at least p blue neighbors and at least one of these blue neighbors of v has at most q white neighbors, then by the spreading color change rule the vertex v is recolored blue. The initial set S of blue vertices is a (p, q)-spreading set for G if by repeatedly applying the spreading color change rule all the vertices of G are eventually colored blue. The (p, q)-spreading set is a generalization of the well-studied concepts of k-forcing and r-percolating sets in graphs. For q ≥ 2, a (1, q)-spreading set is exactly a q-forcing set, and the (1, 1)-spreading set is a 1-forcing set (also called a zero forcing set), while for q = ∞, a (p,∞)-spreading set is exactly a p-percolating set. The (p, q)-spreading number, σ(p,q)(G), of G is the minimum cardinality of a (p, q)-spreading set. In this paper, we study (p, q)-spreading in claw-free cubic graphs. While the zero-forcing number of claw-free cubic graphs was studied earlier, for each pair of values p and q that are not both 1 we either determine the (p, q)-spreading number of a claw-free cubic graph G or show that σ(p,q)(G) attains one of two possible values.

Słowa kluczowe

EN

bootstrap percolation; zero forcing set; k-forcing set; spreading

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 5
• Strony: 581--600
• Opis fizyczny: Bibliogr. 26 poz., tab., wykr.

Twórcy

autor

Brešar Boštjan

• University of Maribor, Faculty of Natural Sciences and Mathematics, Maribor, Slovenia
• Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

• https://orcid.org/0000-0001-8471-4796

autor

Hedžet Jaka

• University of Maribor, Faculty of Natural Sciences and Mathematics, Maribor, Slovenia
• Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

• https://orcid.org/0009-0009-5723-8603

autor

Henning Michael A.

• University of Johannesburg, Department of Mathematics and Applied Mathematics, Johannesburg, South Africa

• https://orcid.org/0000-0001-8185-067X

Bibliografia

• [1] A. Aazami, Hardness results and approximation algorithms for some problems on graphs, ProQuest LLC, Ann Arbor, MI, 2009, Thesis (Ph.D.), University of Waterloo (Canada).
• [2] AIM Minimum Rank – Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), 1628–1648.
• [3] D. Amos, Y. Caro, R. Davila, R. Pepper, Upper bounds on the k-forcing number of a graph, Discrete Appl. Math. 181 (2015), 1–10.
• [4] A. Babikir, M.A. Henning, Triangles and (total) domination in subcubic graphs, Graphs Combin. 38 (2022), Paper no. 28, 17 pp.
• [5] A. Babikir, M.A. Henning, Upper total domination in claw-free cubic graphs, Graphs Combin. 38 (2022), Paper no. 172, 15 pp.
• [6] J. Balogh, B. Bollobás, Bootstrap percolation on the hypercube, Probab. Theory Related Fields 134 (2006), 624–648.
• [7] J. Balogh, G. Pete, Random disease on the square grid, Random Str. Alg. 13 (1998), 409–422.
• [8] B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge Univ. Press, New York, 2006.
• [9] B. Brešar, T. Dravec, A. Erey, J. Hedžet, Spreading in graphs, Discrete Appl. Math. 353 (2024), 139–150.
• [10] J. Chalupa, P.L. Leath, G.R. Reich, Bootstrap percolation on a Bethe lattice, J. Physics C: Solid State Physics 12 (1979), L31.
• [11] R. Davila, M.A. Henning, Zero forcing in claw-free cubic graphs, Bull. Malays. Math. Sci. Soc. 43 (2020), 673–688.
• [12] P.J. Dukes, J.A. Noel, A.E. Romer, Extremal bounds for 3-neighbour bootstrap percolation in dimensions two and three, arXiv:2209.07594 19 Sep 2022.
• [13] S.M. Fallat, L. Hogben, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl. 426 (2007) 558–582.
• [14] R.J. Faudree, R.J. Gould, M.S. Jacobson, L.M. Lesniak, T.E. Lindquester, On independent generalized degrees and independence numbers in K(1,m)-free graphs, Discrete Math. 103 (1992), 17–24.
• [15] D. Ferrero, L. Hogben, F. Kenter, M. Young, The relationship between k-forcing and k-power domination, Discrete Math. 341 (2018) 1789–1797.
• [16] M. Gentner, L. Penso, D. Rautenbach, U. Souza, Extremal values and bounds for the zero forcing number, Discrete Appl. Math. 214 (2016), 196–200.
• [17] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs: Core Concepts, Series: Springer Monographs in Mathematics, Springer, Cham, 2023.
• [18] M. He, H. Li, N. Song, S. Ji, The zero forcing number of claw-free cubic graphs, Discrete Appl. Math. 359 (2024), 321–330.
• [19] J. Hedžet, M.A. Henning, 3-neighbor bootstrap percolation on grids, Discuss. Math. Graph Theory 45 (2025), 283–310.
• [20] M.A. Henning, C. Löwenstein, Locating-total domination in claw-free cubic graphs, Discrete Math. 312 (2012), 3107–3116.
• [21] L. Hogben, J.C.-H. Lin, B.L. Shader, Inverse problems and zero forcing for graphs, Mathematical Surveys and Monographs 270, American Mathematical Society, Providence, 2022.
• [22] T. Kalinowski, N. Kamčev, B. Sudakov, The zero forcing number of graphs, SIAM J. Discrete Math. 33 (2019), 95–115.
• [23] H. Li, C. Virlouvet, Neighborhood conditions for claw-free Hamiltonian graphs, Twelfth British Combinatorial Conference (Norwich, 1989), Ars Combin. 29 (1990), 109–116.
• [24] G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B 28 (1980), 284–304.
• [25] E. Riedl, Largest and smallest minimal percolating sets in trees, Electron. J. Combin. 19 (2012), #P64.
• [26] A.E. Romer, Tight bounds on 3-neighbor bootstrap percolation, Master’s Thesis, University of Victoria, Victoria, Canada, 2022.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)