@article{23001,
  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.},
  author       = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien and Wang, Yiting},
  issn         = {1098-2418},
  journal      = {Random Structures and Algorithms},
  number       = {2},
  publisher    = {Wiley},
  title        = {{Approximate Itai–Zehavi conjecture for random graphs}},
  doi          = {10.1002/rsa.70095},
  volume       = {69},
  year         = {2026},
}