2
$\begingroup$

Let $(N,E)$ a directed graph in which, if $a$ is reachable from $b$, then $b$ is also reachable from $a$. In other words, if $a$ and $b$ lie on a common path, then they also lie on a common cycle.

Clearly, this is the case for any undirected graph (the cycle formulation doesn't work then), but in general not for directed graphs.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

You could say that a digraph has this property if and only if all connected components are strongly connected. I'm not sure if there is one word for it.

$\endgroup$

You must log in to answer this question.

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