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.


  • 1
    $\begingroup$ K edge connectedness / vertex connectedness . $\endgroup$
    – Pushpa
    Mar 3, 2016 at 5:17

1 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.


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).


You must log in to answer this question.

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