On the superconnectivity and the conditional diameter of graphs and digraphs

It has been proved that if the diameter D of a digraph G satisfies D less t han or equal to 2l - 2, where l is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogou sly, if D less than or equal to 2l - 1, then G is edge-superconnected. In t his paper, we studied some similar conditions for a digraph to attain super connectivity, which are given in terms of the conditional diameter or P-dia meter of G, This parameter measures how far apart can be a pair of subdigra phs satisfying a given property P, and, hence, it generalizes the standard concept of the diameter. As a corollary, some new sufficient conditions to attain superconnectivity or edge-superconnectivity are derived. It is also shown that these conditions can be slightly relaxed when the digraphs are b ipartite. The case of (undirected) graphs is managed as a corollary of the above results for digraphs. (C) 1999 John Wiley & Sons, Inc.