Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2512.01429 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909937775411200 |
|---|---|
| author | Jelassi, Mehdi Portier, Julien Sarkar, Rik |
| author_facet | Jelassi, Mehdi Portier, Julien Sarkar, Rik |
| contents | We study the probabilistic zero forcing process, a probabilistic variant of the classical zero forcing process. We show that for every connected graph $G$ on $n$ vertices, there exists an initial set consisting of a single vertex such that the expected propagation time is $n/2 + O(1)$. This result is tight and confirms a conjecture posed by Narayanan and Sun. Additionally, we show tight bounds on the probabilistic throttling number, which captures the trade-off between the size of the initial set and the speed of propagation. Namely, we show that for every connected graph $G$ on $n$ vertices, there exists an initial set consisting of $O(\sqrt{n})$ vertices such that the expected propagation time is $O(\sqrt{n})$. This improves upon previous results by Geneson and Hogben, and confirms another conjecture by Narayanan and Sun. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01429 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight bounds for expected propagation time of probabilistic zero forcing Jelassi, Mehdi Portier, Julien Sarkar, Rik Combinatorics Probability We study the probabilistic zero forcing process, a probabilistic variant of the classical zero forcing process. We show that for every connected graph $G$ on $n$ vertices, there exists an initial set consisting of a single vertex such that the expected propagation time is $n/2 + O(1)$. This result is tight and confirms a conjecture posed by Narayanan and Sun. Additionally, we show tight bounds on the probabilistic throttling number, which captures the trade-off between the size of the initial set and the speed of propagation. Namely, we show that for every connected graph $G$ on $n$ vertices, there exists an initial set consisting of $O(\sqrt{n})$ vertices such that the expected propagation time is $O(\sqrt{n})$. This improves upon previous results by Geneson and Hogben, and confirms another conjecture by Narayanan and Sun. |
| title | Tight bounds for expected propagation time of probabilistic zero forcing |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2512.01429 |