Maximally edge-connected and vertex-connected graphs and digraphs: A survey Original Research Article

Let D be a graph or a digraph. If image is the minimum degree, image the edge-connectivity and image the vertex-connectivity, then image is a well-known basic relationship between these parameters. The graph or digraph D is called maximally edge-connected if image and maximally vertex-connected if image. In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively.