14
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ I wonder if anyone else has also spent the last 2 hours attempting counterexamples :( $\endgroup$
    – Vidit Nanda
    Commented Jun 5, 2012 at 22:05
  • $\begingroup$ Should the two directed spanning trees comprising D have the same root? $\endgroup$
    – Benjamin Young
    Commented Jun 7, 2012 at 16:38
  • $\begingroup$ Dear Benjamin, not at all. $\endgroup$
    – Gil Kalai
    Commented Jun 7, 2012 at 19:28
  • $\begingroup$ 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? $\endgroup$
    – Flo Pfender
    Commented Jun 8, 2012 at 8:04
  • 5
    $\begingroup$ Where is the example of Chudnovsky & Seymour? $\endgroup$
    – Gerry Myerson
    Commented Aug 12, 2014 at 1:42

0

Reset to default

You must log in to answer this question.