# Independent trees

In a graph G=(V,E) with a root node r, two spanning trees $T_1$ and $T_2$ are called r-independent if for any node x in V-r, the unique paths between r and x in $T_1$ and $T_2$ 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 $k\geq 5$ the problem is still open.

Concerning planar graphs, Huck proved[5][6] the statement for each $k\geq1$, i.e. we have

Theorem For a rooted k-connected undirected planar multigraph and $r\in V(G)$ 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 $r\in V(G)$ and $k\in\{1,2\}\cup\{6,7,8,...\}$ such that D is planar if $k\geq 6$. Then D contains k independent spanning arborescences of root r.

(ii) Let G be a rooted k-connected undirected multigraph for some root $r\in V(G)$ and $k\geq 1$ such that G is planar if $k\geq 5$. 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 $T_1$ and $T_2$ are called strongly independent if for any two nodes x,y in V, the unique paths between x and y in $T_1$ and $T_2$ 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

1. 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.
2. 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.
3. A. Itai, A. Zehavi, Three tree-paths, Journal of Graph Theory 13 (1989), pp. 175-188. Author link.
4. S. Curran, O. Lee, X. Yu, Finding Four Independent Trees, SIAM J. Computing 35 (2006), pp. 1023-1058.DOI link.
5. A. Huck, Independent trees in planar graphs, Graphs and Combinatorics 15 (1999), 29-77, DOI link.
6. A. Huck, Independent trees in graphs, Graphs and Combinatorics 10 (1994), pp. 29-45. DOI link.
7. A. Huck, Independent trees and branchings in Planar Multigraphs, Graphs and Combinatorics 15 (1999), pp. 211-220. DOI link.
8. 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
9. F. Péterfalvi: Two counterexamples on completely independent spanning trees, Discrete Mathematics (2012). DOI link, EGRES Technical Report