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.
See also
Edge-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
