The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n , minimum degree δ, maximum degree Δ, diameter D , and a new parameter l pi; , 0 ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs l 0 = ⌊( g − 1)/2⌋ where g stands for the girth). For instance, let G = ( V,A ) be a digraph on n vertices with maximum degree Δ and diameter D , so that n ≤ n (Δ, D ) = 1 + Δ + Δ 2 + … + Δ D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc‐connectivity of G ,. Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.