Bootstrap Percolation, Connectivity, and Graph Distance
| Autor: | LaFayette, Hudson, Ibrahim, Rayan, McCall, Kevin |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Bootstrap Percolation is a process defined on a graph which begins with an initial set of infected vertices. In each subsequent round, an uninfected vertex becomes infected if it is adjacent to at least $r$ previously infected vertices. If an initially infected set of vertices, $A_0$, begins a process in which every vertex of the graph eventually becomes infected, then we say that $A_0$ percolates. In this paper we investigate bootstrap percolation as it relates to graph distance and connectivity. We find a sufficient condition for the existence of cardinality 2 percolating sets in diameter 2 graphs when $r = 2$. We also investigate connections between connectivity and bootstrap percolation and lower and upper bounds on the number of rounds to percolation in terms of invariants related to graph distance. Comment: 18 pages, 11 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|