Edge-independent spanning trees
In a graph G=(V,E) with a root node r, two spanning trees [math]T_1[/math] and [math]T_2[/math] are called edge-independent if for any node x in V-r, the unique paths between r and x in [math]T_1[/math] and [math]T_2[/math] are edge-disjoint. Is it true that if G is k-edge-connected then there exist k edge-independent spanning trees for arbitrary r?
Remarks
The conjecture was proposed by Itai and Zehavi [1] as an edge-connectivity variant of the independent tree conjecture. Khuller and Scheiber [2] claimed that the vertex-connectivity version of the conjecture implies the edge-connectivity version; however, their proof was shown to be incorrect by Gopalan and Ramasubramanian [3]. The latter proved the case k=3, while Hoyer and Thomas [4] proved the conjecture for k=4.
See also
References
- ↑ A. Itai, A. Zehavi, Three tree-paths, 1989, DOI link, Author link.
- ↑ S. Khuller, B. Schieber, On independent spanning trees, 1992, DOI link
- ↑ A. Gopalan, S. Ramasubramanian, On constructing three edge independent spanning trees, 2011, semanticscholar link
- ↑ A. Hoyer, R. Thomas, Four Edge-Independent Spanning Trees, 2018, DOI link, arXiv link
