| Naslov: | Bootstrap percolation and $P_3$-hull number in direct products of graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Hedžet, Jaka (Avtor)
ID Herrman, Rebekah (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (258,32 KB)
MD5: 14F225AC90C53D79CAFEE1389744DDC6
 URL - Izvorni URL, za dostop obiščite https://www.dmgt.uz.zgora.pl/publish/article.php?doi=2603
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | The $r$-neighbor bootstrap percolation is a graph infection process based on the update rule by which a vertex with $r$ infected neighbors becomes infected. We say that an initial set of infected vertices propagates if all vertices of a graph $G$ are eventually infected, and the minimum cardinality of such a set in $G$ is called the $r$-bootstrap percolation number, $m(G,r)$, of $G$. In this paper, we study percolating sets in direct products of graphs. While in general graphs there is no non-trivial upper bound on $m(G\times H,r)$, we prove several upper bounds under the assumption $\delta(G)\ge r$. We also characterize the connected graphs $G$ and $H$ with minimum degree $2$ that satisfy $m(G \times H, 2) = \frac{|V(G \times H)|}{2}$. In addition, we determine the exact values of $m(P_n \times P_m, 2)$, which are $m+n-1$ if $m$ and $n$ are of different parities, and $m+n$ otherwise.
|
|---|
| Ključne besede: | bootstrap percolation, direct product of graphs, $P_3$-convexity |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | str. 257-278 |
|---|
| Številčenje: | Vol. 46, no. 1 |
|---|
| PID: | 20.500.12556/DiRROS-25333  |
|---|
| UDK: | 519.17:519.2 |
|---|
| ISSN pri članku: | 1234-3099 |
|---|
| DOI: | 10.7151/dmgt.2603 |
|---|
| COBISS.SI-ID: | 264957187 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 16.01.2026 |
|---|
| Število ogledov: | 362 |
|---|
| Število prenosov: | 243 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
