| Title: | Spreading in claw-free cubic graphs |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Hedžet, Jaka (Author)
ID Henning, Michael A. (Author) |
|---|
| Files: |  PDF - Presentation file, download (530,15 KB)
MD5: 9A39310687CBE79264838F22D35677BA
 URL - Source URL, visit https://www.opuscula.agh.edu.pl/om-vol45iss5art1
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | Let $p\in\mathbb{N}$ and $q\in\mathbb{N}\cup\{\infty\}$. 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\ge2$, 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 |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | str. 581-600 |
|---|
| Numbering: | Vol. 45, no. 5 |
|---|
| PID: | 20.500.12556/DiRROS-23662  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1232-9274 |
|---|
| DOI: | 10.7494/OpMath.2025.45.5.581 |
|---|
| COBISS.SI-ID: | 249948163 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 23.09.2025 |
|---|
| Views: | 219 |
|---|
| Downloads: | 105 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
