article published yes Lawrence Hollom author Lyuben Lichev author 9aa8388e-d003-11ee-8458-c4c1d7447977 Adva Mond author Julien Portier author Yiting Wang author 1917d194-076e-11ed-97cd-837255f88785 MaKw department GradSch department Randomness and structure in combinatorics project A famous conjecture by Itai and Zehavi states that, for every 𝑑 -vertex-connected graph 𝐺 and every vertex 𝑟 in 𝐺 , there are 𝑑 spanning trees of 𝐺 such that, for every vertex 𝑣 in 𝐺 ∖{𝑟} , the paths between 𝑟 and 𝑣 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 𝐺⁡(𝑛,𝑝) when 𝑛⁢𝑝 =𝜔⁡(log⁡𝑛) and for random regular graphs 𝐺⁡(𝑛,𝑑) when 𝑑 =𝜔⁡(log⁡𝑛) . Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers a question of Draganić and Krivelevich positively. Our proof makes use of recent developments on sprinkling techniques in random regular graphs. https://research-explorer.ista.ac.at/download/23001/23068/2026_RandomStructAlgorithms_Hollom.pdf application/pdfno Wiley2026 eng 1042-9832 1098-2418 2506.2397010.1002/rsa.70095 692 L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Approximate Itai–Zehavi conjecture for random graphs,” <i>Random Structures and Algorithms</i>, vol. 69, no. 2. Wiley, 2026. Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. 69(2), e70095. Hollom, L., Lichev, L., Mond, A., Portier, J., &#38; Wang, Y. (2026). Approximate Itai–Zehavi conjecture for random graphs. <i>Random Structures and Algorithms</i>. Wiley. <a href="https://doi.org/10.1002/rsa.70095">https://doi.org/10.1002/rsa.70095</a> L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Random Structures and Algorithms 69 (2026). Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Approximate Itai–Zehavi Conjecture for Random Graphs.” <i>Random Structures and Algorithms</i>. Wiley, 2026. <a href="https://doi.org/10.1002/rsa.70095">https://doi.org/10.1002/rsa.70095</a>. Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture for random graphs. <i>Random Structures and Algorithms</i>. 2026;69(2). doi:<a href="https://doi.org/10.1002/rsa.70095">10.1002/rsa.70095</a> Hollom, Lawrence, et al. “Approximate Itai–Zehavi Conjecture for Random Graphs.” <i>Random Structures and Algorithms</i>, vol. 69, no. 2, e70095, Wiley, 2026, doi:<a href="https://doi.org/10.1002/rsa.70095">10.1002/rsa.70095</a>. 230012026-09-27T22:01:52Z2026-10-07T07:13:30Z