| Naslov: | Spreading in claw-free cubic graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Hedžet, Jaka (Avtor)
ID Henning, Michael A. (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (530,15 KB)
MD5: 9A39310687CBE79264838F22D35677BA
 URL - Izvorni URL, za dostop obiščite https://www.opuscula.agh.edu.pl/om-vol45iss5art1
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | bootstrap percolation, zero forcing set, k-forcing set, spreading |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | str. 581-600 |
|---|
| Številčenje: | Vol. 45, no. 5 |
|---|
| PID: | 20.500.12556/DiRROS-23662  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1232-9274 |
|---|
| DOI: | 10.7494/OpMath.2025.45.5.581 |
|---|
| COBISS.SI-ID: | 249948163 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 23.09.2025 |
|---|
| Število ogledov: | 220 |
|---|
| Število prenosov: | 106 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
