0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

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