Edge-independent spanning trees

From Egres Open
Jump to: navigation, search

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?


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

Independent trees


  1. A. Itai, A. Zehavi, Three tree-paths, 1989, DOI link, Author link.
  2. S. Khuller, B. Schieber, On independent spanning trees, 1992, DOI link
  3. A. Gopalan, S. Ramasubramanian, On constructing three edge independent spanning trees, 2011, semanticscholar link
  4. A. Hoyer, R. Thomas, Four Edge-Independent Spanning Trees, 2018, DOI link, arXiv link