Approximate Itai–Zehavi conjecture for random graphs
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.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Hollom, Lawrence;
Lichev, LyubenISTA;
Mond, Adva;
Portier, Julien;
Wang, YitingISTA
Department
Abstract
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.
Publishing Year
Date Published
2026-09-01
Journal Title
Random Structures and Algorithms
Publisher
Wiley
Acknowledgement
Hollom was supported by the Internal Graduate Studentship of Trinity College, Cambridge. Mond was supported by UK Research and Innovation grant MR/W007320/2. Wang was supported by the ERC Starting Grant “RANDSTRUCT” No. 101076777. Lichev was supported by the Austrian Science Fund (FWF) [10.55776/ESP624]. For open access purposes, the authors have applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. Open Access funding provided by Technische Universitat Wien.
Part of this research was done during a visit of the fourth author to IST Austria. We thank IST Austria for its hospitality. We also thank the anonymous referees for their comments and suggestions. Open Access funding provided by Technische Universitat Wien. This work was supported by the European Research Council, UK Research and Innovation, the Austrian Science Fund, and Trinity College.
Volume
69
Issue
2
Article Number
e70095
ISSN
eISSN
IST-REx-ID
Cite this
Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. 2026;69(2). doi:10.1002/rsa.70095
Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.70095
Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Approximate Itai–Zehavi Conjecture for Random Graphs.” Random Structures and Algorithms. Wiley, 2026. https://doi.org/10.1002/rsa.70095.
L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Approximate Itai–Zehavi conjecture for random graphs,” Random Structures and Algorithms, 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, Lawrence, et al. “Approximate Itai–Zehavi Conjecture for Random Graphs.” Random Structures and Algorithms, vol. 69, no. 2, e70095, Wiley, 2026, doi:10.1002/rsa.70095.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2026_RandomStructAlgorithms_Hollom.pdf
457.58 KB
Access Level
Open Access
Date Uploaded
2026-10-07
MD5 Checksum
9a786460a47542f24576e947987e558a
arXiv 
Google Scholar