Approximate Itai-Zehavi conjecture for random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915365557108736 |
|---|---|
| author | Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting |
| author_facet | Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting |
| contents | A famous conjecture by Itai and Zehavi states that, for every $d$-vertex-connected graph $G$ and every vertex $r$ in $G$, there are $d$ spanning trees of $G$ such that, for every vertex $v$ in $G\setminus \{r\}$, the paths between $r$ and $v$ in different trees are internally vertex-disjoint. We show that with high probability the Itai-Zehavi conjecture holds asymptotically for the Erdős-Rényi random graph $G(n,p)$ when $np= ω(\log n)$ and for random regular graphs $G(n,d)$ when $d= ω(\log n)$. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers positively a question of Draganić and Krivelevich. Our proof makes use of recent developments on sprinkling techniques in random regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23970 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate Itai-Zehavi conjecture for random graphs Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting Combinatorics A famous conjecture by Itai and Zehavi states that, for every $d$-vertex-connected graph $G$ and every vertex $r$ in $G$, there are $d$ spanning trees of $G$ such that, for every vertex $v$ in $G\setminus \{r\}$, the paths between $r$ and $v$ in different trees are internally vertex-disjoint. We show that with high probability the Itai-Zehavi conjecture holds asymptotically for the Erdős-Rényi random graph $G(n,p)$ when $np= ω(\log n)$ and for random regular graphs $G(n,d)$ when $d= ω(\log n)$. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers positively a question of Draganić and Krivelevich. Our proof makes use of recent developments on sprinkling techniques in random regular graphs. |
| title | Approximate Itai-Zehavi conjecture for random graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.23970 |