1
$\begingroup$

I know that an undirected connected graph allows a strongly connected orientation if it does not contain a bridge.

I am curious in the sort of opposite question, given a directed graph for which the undirected graph is connected, when is that directed graph strongly connected?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ If the underlying undirected graph is disconnected, then obviously the digraph cannot be strongly connected. So your question is basically asking when a digraph is strongly connected. This is true if and only if it does not contain a directed cut. $\endgroup$
    – Tony Huynh
    Commented Oct 22, 2021 at 8:22

1 Answer 1

Reset to default
1
$\begingroup$

Trivially:

A digraph $D$ is strongly connected if and only if it satisfies the two conditions:
(i) the underlying graph of $D$ is connected;
(ii) every arc in $D$ is part of a directed cycle.

If a finite digraph has a connected underlying graph, and if each vertex has equal indegree and outdegree, then it is strongly connected.

Are you looking for something deeper?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .