Maximally edge-connected and vertex-connected graphs and digraphs: A survey

Let D   be a graph or a digraph. If δ(D)δ(D) is the minimum degree, λ(D)λ(D) the edge-connectivity and κ(D)κ(D) the vertex-connectivity, then κ(D)⩽λ(D)⩽δ(D)κ(D)⩽λ(D)⩽δ(D) is a well-known basic relationship between these parameters. The graph or digraph D   is called maximally edge-connected if λ(D)=δ(D)λ(D)=δ(D) and maximally vertex-connected if κ(D)=δ(D)κ(D)=δ(D). 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.