On Independent Spanning Trees in Random and Pseudorandom Graphs

In 1989, Zehavi and Itai conjectured that every k-connected graph contains k independent spanning trees rooted at any prescribed vertex r. That is, for each vertex v, the unique r-v paths within these k spanning trees are internally disjoint. This fundamental problem has received much attention, in part motivated by its applications to network reliability, but despite that has only been resolved for k 4 and certain restricted graph families. We establish the conjecture for almost all graphs of essentially any relevant density. Specifically, we prove that there exists a constant C > 1 such that, with high probability, the random graph G (n, p) contains δ (G) independent spanning trees rooted at any vertex whenever C n/n p < 0. 99. Since the lower bound on p coincides (up to the constant C) with the connectivity threshold of G (n, p), this result is essentially optimal. In addition, we show that (n, d, λ) -graphs with fairly mild bounds on the spectral ratio d/λ contain (1-o (1) ) d independent spanning trees rooted at each vertex, thereby settling the conjecture asymptotically for random d-regular graphs as well.