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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.