Superconnected digraphs and graphs with small conditional diameters

The conditional diameter D ν of a digraph G measures how far apart a pair of vertex sets V 1 and V 2 can be in such a way that the minimum out‐degree and the minimum in‐degree of the subdigraphs induced by V 1 and V 2 , respectively, are at least ν. Thus, D 0 is the standard diameter and D 0 ≥ D 1 ≥ ··· ≥ D δ , where δ is the minimum degree. We prove that if D ν ≤ 2l − 3, where l is a parameter related to the shortest paths, then G is maximally connected, is superconnected, or has a good superconnectivity, depending only on whether ν is equal to ⌈δ/2⌉, ⌈(δ − 1)/2⌉, or ⌈(δ − 1)/3⌉, respectively. In the edge case, it is enough that D ν ≤ 2l − 2. The results for graphs are obtained as a corollary of those for digraphs, because, in the undirected case, l = ⌊( g − 1)/2⌋, g being the girth. © 2002 Wiley Periodicals, Inc.