# Independent 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 *r*-**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 internally node disjoint. Is it true that if *G* is *k*-connected then there exist *k* *r*-independent trees for arbitrary *r*?

## Remarks

It has been showed^{[1]}^{[2]}^{[3]} that the conjecture holds for *k=2,3*. The case when *k=4* was also verified^{[4]} but for [math]k\geq 5[/math] the problem is still open.

Concerning planar graphs, Huck proved^{[5]}^{[6]} the statement for each [math]k\geq1[/math],
i.e. we have

**Theorem** For a rooted *k*-connected undirected planar multigraph and [math]r\in V(G)[/math] there exist *k* *r*-independent spanning trees in *G*.

Planar multigraphs are handleable even in the directed case. Huck proved^{[7]} a strengthening of these theorems where the connectivity condition is weakened to rooted connectivity. By summarizing the mentioned results we have the following.

**Theorem**

(i) Let *D* be a rooted *k*-connected directed multigraph for some root [math]r\in V(G)[/math] and
[math]k\in\{1,2\}\cup\{6,7,8,...\}[/math] such that *D* is planar if [math]k\geq 6[/math]. Then *D* contains *k*
independent spanning arborescences of root *r*.

(ii) Let *G* be a rooted *k*-connected undirected multigraph for some root [math]r\in V(G)[/math] and
[math]k\geq 1[/math] such that *G* is planar if [math]k\geq 5[/math]. Then *G* contains *k* *r*-independent spanning
trees.

### Strongly independent spanning trees

A further strengthening of this concept is **strongly independent trees**: two spanning trees [math]T_1[/math] and [math]T_2[/math] are called **strongly independent** if for any two nodes *x,y* in *V*, the unique paths between *x* and *y* in [math]T_1[/math] and [math]T_2[/math] are internally node disjoint.
Hasunuma^{[8]} posed the following conjecture:

**Conjecture.** Is it true that any *2k*-connected graph contains *k* strongly independent spanning trees?

This has been disproved by Péterfalvi^{[9]} by showing that for any *k* there exist a *k*-connected graph not containing two strongly independent spanning trees.

## References

- ↑ J. Cheriyan, S.N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms 9 (1988), pp. 507-537. DOI link.
- ↑ A. Itai, R. Rodeh, The multi-tree approach to reliability in distributed networks, Proceedings 25th Annual IEEE Symposium on Foundations of Computer Sciences (1984), pp. 137-147. Author link.
- ↑ A. Itai, A. Zehavi, Three tree-paths, Journal of Graph Theory 13 (1989), pp. 175-188. Author link.
- ↑ S. Curran, O. Lee, X. Yu, Finding Four Independent Trees, SIAM J. Computing 35 (2006), pp. 1023-1058.DOI link.
- ↑ A. Huck, Independent trees in planar graphs, Graphs and Combinatorics 15 (1999), 29-77, DOI link.
- ↑ A. Huck, Independent trees in graphs, Graphs and Combinatorics 10 (1994), pp. 29-45. DOI link.
- ↑ A. Huck, Independent trees and branchings in Planar Multigraphs, Graphs and Combinatorics 15 (1999), pp. 211-220. DOI link.
- ↑ Hasunuma: Completely independent spanning trees in maximal planar graphs, Proc. 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2002), Lecture Notes in Comput. Sci. 2573, pp. 235-245, 2002, Springer DOI link
- ↑ F. Péterfalvi: Two counterexamples on completely independent spanning trees, Discrete Mathematics (2012). DOI link, EGRES Technical Report