Spreading in claw-free cubic graphs

Boštjan Brešar
Jaka Hedžet
Michael A. Henning

Abstract. 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.

Keywords: bootstrap percolation, zero forcing set, \(k\)-forcing set, spreading.

Mathematics Subject Classification: 05C35, 05C75.

Full text (pdf)