Critical threshold for regular graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910777441517568 |
|---|---|
| author | Bhadoo, Ishaan |
| author_facet | Bhadoo, Ishaan |
| contents | In this article, we study the critical percolation threshold $p_c$ for $d$-regular graphs. It is well-known that $p_c \geq \frac{1}{d-1}$ for such graphs, with equality holding for the $d$-regular tree. We prove that among all quasi-transitive $d$-regular graphs, the equality $p_c(G) = \frac{1}{d-1}$ holds if and only if $G$ is a tree. Furthermore, we provide counterexamples that illustrate the necessity of the quasi-transitive assumption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00635 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Critical threshold for regular graphs Bhadoo, Ishaan Probability Combinatorics In this article, we study the critical percolation threshold $p_c$ for $d$-regular graphs. It is well-known that $p_c \geq \frac{1}{d-1}$ for such graphs, with equality holding for the $d$-regular tree. We prove that among all quasi-transitive $d$-regular graphs, the equality $p_c(G) = \frac{1}{d-1}$ holds if and only if $G$ is a tree. Furthermore, we provide counterexamples that illustrate the necessity of the quasi-transitive assumption. |
| title | Critical threshold for regular graphs |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2412.00635 |