Connectedness of digraphs and graphs under constraints on the conditional diameter

Given a digraph G with minimum degree δ and an integer 0≤ ν ≤ δ , consider every pair of vertex subsets V 1 and V 2 such that both the minimum out‐degree of the induced subdigraph G [ V 1 ] and the minimum in‐degree of G [ V 2 ] are at least ν . The conditional diameter D ν of G is defined as the maximum of the distances d ( V 1 , V 2 ) between any two such vertex subsets. Clearly, D 0 is the standard diameter and D 0 ≥ D 1 ≥ ··· ≥ D δ holds. In this article, we guarantee appropriate lower bounds for the connectivities and superconnectivities of a digraph G when D ν ≤ h ( ℓ π ), h ( ℓ π ) being a function of the parameter ℓ π —which is related to the shortest paths in G . As a corollary of these results, we give some constraints of the kind D ν ≤ h ( ℓ π ), which assure that the digraph is maximally connected, maximally edge‐connected, superconnected, or edge‐superconnected, extending other previous results of the same kind. Similar statements can be obtained for a graph as a direct consequence of those for its associated symmetric digraph. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 80–87 2005