Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed spanning trees. Suppose that

There no subset X of vertices so that there is precisely one directed edge from X to its complement and one directed edge from the complement of X to X.

Is it true that D has a directed spanning tree T, T is a subset of E, such that E-T is also a directed spanning tree and reversing the orientation of each edge of T results in a strongly connected digraph?

update:

The answer is NO as pointed out by an example by Maria Chudnovsky and Paul Seymour, who also pointed out additional necessary conditions. A remaining question is:

Problem: Find a characterization of directed graphs $D$ that has a spanning tree $T$, such that $E-T$ is also a spanning tree and reversing the orientation of each edge of $T$ results in a strongly connected digraph

share|improve this question
3  
I wonder if anyone else has also spent the last 2 hours attempting counterexamples :( –  Vidit Nanda Jun 5 '12 at 22:05
    
Should the two directed spanning trees comprising D have the same root? –  Benjamin Young Jun 7 '12 at 16:38
    
Dear Benjamin, not at all. –  Gil Kalai Jun 7 '12 at 19:28
    
Gil, when you say "directed trees", do you mean 1) rooted tree, and all edges directed away from it, or 2) tree with all edges directed some way? –  Flo Pfender Jun 8 '12 at 8:04
1  
Where is the example of Chudnovsky & Seymour? –  Gerry Myerson Aug 12 at 1:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.