TY  - JOUR
ID  - Brešar2025
LB  - Brešar2025
AU  - Brešar, Boštjan
AU  - Hedžet, Jaka
AU  - Henning, Michael A.
TI  - Spreading in claw-free cubic graphs
ST  - Spreading in claw-free cubic graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2025
VL  - 45
IS  - 5
SP  - 581
EP  - 600
DO  - https://doi.org/10.7494/OpMath.2025.45.5.581
UR  - https://doi.org/10.7494/OpMath.2025.45.5.581
AB  - Let \(p \in \mathbb{N}\) and \(q \in \mathbb{N} \cup \lbrace \infty \rbrace\). 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 \geq 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 = \infty\), a \((p,\infty)\)-spreading set is exactly a \(p\)-percolating set. The \((p,q)\)-spreading number, \(\sigma_{(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 \(\sigma_{(p,q)}(G)\) attains one of two possible values.
KW  - bootstrap percolation
KW  - zero forcing set
KW  - \(k\)-forcing set
KW  - spreading
SN  - 1232-9274
ER  -