Disjoint strongly connected spanning subgraphs
Does there exist a value k so that every k-arc-connected directed graph contains a pair of arc-disjoint strongly connected spanning sub-digraphs?
Remarks
The conjecture was proposed by Bang-Jensen and Yeo [1], and they proved several cases involving semicomplete digraphs. Yeo showed that it is NP-complete to decide whether a 2-regular digraph has two arc-disjoint strongly connected spanning subdigraphs ([2], Theorem 13.10.1).
Related questions
A similar question can be asked about Disjoint spanning in- and out-arborescences, and several related problems are mentioned in the survey of Bang-Jensen and Kriesell [3]. For example, the following weaker conjecture is also open:
Is there an integer [math]k[/math] such that every [math]k[/math]-arc-connected directed graph can be decomposed into a strongly connected spanning sub-digraph and a weakly connected spanning sub-digraph?
References
- ↑ J. Bang-Jensen, A. Yeo, Decomposing k-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24 (2004), 331-349. DOI link. Eprint link.
- ↑ J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd edition, Springer Verlag (2008). Google Books link.
- ↑ J. Bang-Jensen, M. Kriesell, Disjoint sub(di)graphs in digraphs, Electronic Notes in Discrete Mathematics 34 (2009), 179-183. DOI link.
