# Strongly edge-disjoint arborescences

Let *D=(V,A)* be a digraph with a designated root node *r*. We call two arc-disjoint directed paths **strongly edge-disjoint** if they do not contain a pair of symmetric arcs. Two arcs are symmetric if they have the same endnodes but have opposite orientations.
Is it true that there exist *k* arc-disjoint spanning arborescences rooted at *r* such that for every node *v* the paths from *r* to *v* in the arborescences are strongly edge-disjoint if an only if [math]\varrho(X)\geq k[/math] for each nonempty [math]X\subseteq V-r[/math]?

Bérczi and Kovács gave a disproof of the conjecture for [math]k\geq 3[/math] ^{[1]}. They also gave a generalization for the case *k=2*.

## Remarks

The conjecture was proposed by Colussi, Conforti and Zambelli^{[2]} where the case *k=2* was verified. For [math]k\geq 3[/math] the question is still open. It is easy to see that a similar statement holds for strongly edge-disjoint directed *s-t* paths. Hence the conjecture, if it is true, can be considered as a common generalization of Edmonds' disjoint arborescences theorem and Menger's theorem. Note that the conjecture does not require the *k* arborescences to be strongly edge-disjoint, that is, they may share a pair of symmetric arcs.

## References

- ↑ K. Bérczi and E.R. Kovács,
*A note on strongly edge-disjoint arborescences*, Technical Report EGRES 2011-03, Department of Operations Research, Eötvös Loránd University, Budapest, March 2011. PDF - ↑ L. Colussi, M. Conforti and G. Zambelli:
*Disjoint paths in arborescences*, Discrete Mathematics, Volume 292, Issues 1-3, 28 March 2005, Pages 187--191. PDF, DOI link