Superconnected digraphs and graphs with small conditional diameters
Camino Balbuena, Josep M. Fabrega, X. Marcote, Ignacio M. Pelayo · Networks · 2002
Abstract The conditional diameter Dν of a digraph G measures how far apart a pair of vertex sets V1 and V2 can be in such a way that the minimum out‐degree and the minimum in‐degree of the subdigraphs induced by V1 and V2, respectively, are at least ν. Thus, D0 is the standard diameter and D0 ≥ D1 ≥ ··· ≥ 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.