Conjecture on optimal independent spanning trees in Erdős–Rényi graphs
Conjecture on optimal independent spanning trees in Erdős–Rényi graphs
Let be an Erdős–Rényi random graph, and write for its minimum degree. A spanning tree rooted at is an independent spanning tree (IST) family member when the paths from every vertex to in the different trees are pairwise internally vertex-disjoint. Conjecture on optimal independent spanning trees. Fix any . Then, with high probability, for every vertex , the graph contains ISTs rooted at . This would extend the paper's asymptotic result to the threshold regime and attain the natural upper bound supplied by vertex connectivity, which equals the minimum degree in with high probability. The conjecture is posed as an open question.
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.