Conjecture on optimal independent spanning trees in random regular graphs

Let d=d(n)[3,n1]d=d(n)\in[3,n-1], and let GG(n,d)G\sim G(n,d) be a random dd-regular graph. An independent spanning tree (IST) family is a collection of spanning trees whose root-to-vertex paths are pairwise internally vertex-disjoint. Conjecture on optimal independent spanning trees in random regular graphs. With high probability, GG contains dd ISTs if dn3d\neq n-3, and contains d1d-1 ISTs if d=n3d=n-3. The paper identifies this as a strengthening of the sparse random-regular-graph question; the conjecture remains open.

Sources & referencesView supporting material

Primary source

Lawrence Hollom, Lyuben Lichev, Adva Mond, Julien Portier and Yiting Wang, “Approximate Itai-Zehavi conjecture for random graphs”, arXiv:2506.23970 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.