Home » Subject » Graph Theory

Arc-disjoint strongly connected spanning subdigraphs

Importance: Medium ✭✭
Author(s): Bang-Jensen, Joergen
Yeo, Anders
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 2nd, 2013
Conjecture   There exists an ineteger $ k $ so that every $ k $-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

Bang-Jensen and Yeo [BY] proved the conjecture for several classes like tournaments. There is stronger conjecture for tournaments. Yeo (See [BG, Theorem 13.10.1]) showed that it is NP-complete to decide whether a 2-regular digraph has two arc-disjoint strongly connected spanning subdigraphs.

A similar question can be asked about arc-disjoint out-branching and in-branching. Several related problems are mentioned in the survey of Bang-Jensen and Kriesell [BK].

Related problems

Arc-disjoint out-branching and in-branching
Decomposing k-arc-strong tournament into k spanning strong digraphs

Bibliography

[BG] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd. ed., Springer Verlag (2009).

[BK] J. Bang-Jensen, M. Kriesell, Disjoint sub(di)graphs in digraphs, Electronic Notes in Discrete Mathematics 34 (2009), 179-183.

*[BY] J. Bang-Jensen, A. Yeo, Decomposing k-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24 (2004), 331-349.


* indicates original appearance(s) of problem.
add new comment