Definition of vertex-cut for digraph?

264 Views Asked by At

I am trying to understand vertex cut for digraph. I could find this for graphs

Vertex cut is a vertex whose removal increases the number of components in a graph. (D67, Handbook of Graph Theory by Gross)

and components for digraphs defined here. I am interested in st-connectivity so if the digraph definition is analogous with the undirected definition, then the removal of the cut should increase the number of st-connected components. So

What is the definition of vertex-cut for digraph?

1

There are 1 best solutions below

0
On

You can consider the digraph as an undirected graph with the cut-vertex set definition such that

Cut-vertex set of a digraph is a vertex set whose removal increases the number of weakly-connected components.

where the weak connectness. This statement does not work in the case of strong connectness: consider the example on page 165 of the book and remove the vertex set {y,w} in which case the number of components does not increase with strongly connected components.