On Independent Spanning Trees in Random and Pseudorandom Graphs

Abstract

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\le 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 $\hat{I}´(G)$ independent spanning trees rooted at any vertex whenever $C\log n/n\le 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,\hat{I}»)$-graphs with fairly mild bounds on the spectral ratio $d/\hat{I}»$ contain $(1-o(1))d$ independent spanning trees rooted at each vertex, thereby settling the conjecture asymptotically for random $d$-regular graphs as well.

18 pages