Conjecture on optimal independent spanning trees in random regular graphs
Conjecture on optimal independent spanning trees in random regular graphs
Let , and let be a random -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, contains ISTs if , and contains ISTs if . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.