n - Strongly Connected

Question

As i understands :

A diagraph is Strongly Connected if every Node is reachable from every other Node.

Is there any similar notion like k - connectedness for directed graphs.

Thanks

Answer 1

For this and much more on directed graphs, I recommend reading the following book:

• Jørgen Bang-Jensen and Gregory Gutin, Digraphs: Theory, Algorithms and Applications (Second Edition), Springer Monographs in Mathematics.

It is worth mentioning that the First Edition contains some material that didn't make it to the Second Edition, due to space constraints. Both versions however cover $k$-strongly connectedness of directed graphs. The following excerpts are from Section 1.5 (slightly modified for the sake of readability):

For a strongly connected digraph $D = (V,A)$, a set $S \subseteq V$ is a separator if $D - S$ is not strongly connected. A digraph is k-strongly connected (or k-strong) if $|V| \geq k + 1$ and $D$ has no separator with fewer than $k$ vertices. It follows from the definition of strong connectivity that a complete digraph with $n$ vertices is $(n-1)$-strong, but not $n$-strong.

Similarly:

For a pair $s$, $t$ of distinct vertices of a digraph $D$, a set $S \subseteq V(D) - \{s,t\}$ is an (s,t)-separator if $D - S$ has no $(s,t)$-paths. For a strongly connected digraph $D = (V,A)$, a set of arcs $W \subseteq A$ is a cut if $D - A$ is not strongly connected. A digraph $D$ is k-arc-strongly connected (or k-arc-strong) if $D$ has no cut with fewer than $k$ arcs.

Much more on connectivity of directed graphs can be found in Chapter 5 (of the Second Edition) or Chapter 7 (of the First Edition).