On the superconnectivity and the conditional diameter of graphs and digraphs
Ángeles Carmona Mejías, J. F�brega · Networks · 1999
It has been proved that if the diameter D of a digraph G satisfies D ≤ 2ℓ − 2, where ℓ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D ≤ 2ℓ − 1, then G is edge-superconnected. In this paper, we studied some similar conditions for a digraph to attain superconnectivity, which are given in terms of the conditional diameter or 𝒫-diameter of G. This parameter measures how far apart can be a pair of subdigraphs satisfying a given property 𝒫, 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 bipartite. The case of (undirected) graphs is managed as a corollary of the above results for digraphs. © 1999 John Wiley & Sons, Inc. Networks 34: 197–205, 1999