Bootstrap percolation and $P_3$-hull number in direct products of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910370413674496 |
|---|---|
| author | Brešar, Boštjan Hedžet, Jaka Herrman, Rebekah |
| author_facet | Brešar, Boštjan Hedžet, Jaka Herrman, Rebekah |
| contents | 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 $δ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10957 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bootstrap percolation and $P_3$-hull number in direct products of graphs Brešar, Boštjan Hedžet, Jaka Herrman, Rebekah Combinatorics 05C35, 05C76, 60K35 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 $δ(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. |
| title | Bootstrap percolation and $P_3$-hull number in direct products of graphs |
| topic | Combinatorics 05C35, 05C76, 60K35 |
| url | https://arxiv.org/abs/2403.10957 |