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 that the conjecture holds for k=2,3. The case when k=4 was also verified but for $$k\geq 5$$ the problem is still open.

Concerning planar graphs, Huck proved 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 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 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 by showing that for any k there exist a k-connected graph not containing two strongly independent spanning trees.

See also

Edge-independent spanning trees