| Title: | Bootstrap percolation and $P_3$-hull number in direct products of graphs |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Hedžet, Jaka (Author)
ID Herrman, Rebekah (Author) |
|---|
| Files: |  PDF - Presentation file, download (258,32 KB)
MD5: 14F225AC90C53D79CAFEE1389744DDC6
 URL - Source URL, visit https://www.dmgt.uz.zgora.pl/publish/article.php?doi=2603
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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.
|
|---|
| Keywords: | bootstrap percolation, direct product of graphs, $P_3$-convexity |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | str. 257-278 |
|---|
| Numbering: | Vol. 46, no. 1 |
|---|
| PID: | 20.500.12556/DiRROS-25333  |
|---|
| UDC: | 519.17:519.2 |
|---|
| ISSN on article: | 1234-3099 |
|---|
| DOI: | 10.7151/dmgt.2603 |
|---|
| COBISS.SI-ID: | 264957187 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 16.01.2026 |
|---|
| Views: | 323 |
|---|
| Downloads: | 233 |
|---|
| 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. |
