The connectivity of large digraphs and graphs
Miquel Àngel Fiol · Journal of Graph Theory · 1993
Abstract 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 lpi;, 0 ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs l0 = ⌊(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, equation image . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.