SPREADING IN CLAW-FREE CUBIC GRAPHS

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.