Skip to main content
MathOverflow

Return to Question

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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:

###update: TheThe 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

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

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

added 410 characters in body
Source Link
Gil Kalai
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

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

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?

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

Source Link
Gil Kalai
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

A Conjecture About Directed Graphs that are the Union of Two Trees

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?