Super edge-connectivity of dense digraphs and graphs

AbstractSuper-λ is a more refined network reliability index than edge-connectivity. A graph is super-λ if every minimum edge-cut set is trivial (the set of edges incident at a node with the minimum degree δ). This paper establishes the relation between diameter and super-λ: enlarging the order n under the given maximum degree Δ and diameter D not only maximizes edge-connectivity, but also minimizes the number of minimum edge-cut sets, thus attaining super-λ. The following sufficient conditions for a diagraph and graph G to be super-λ are derived. •• Digraph G is super-λ if n>δ((ΔD−1−1)(Δ−1)+1)+ΔD−1.•• Graph G is super-λ if n>δ(((Δ−1)D−1−1)(Δ−2)+1)+(Δ−1)D−1.These conditions are the best possible. From these, the de Bruijn digraph B(d,D),the Kautz digraph K(d, D), and most of the densest known graphs (listed in [3, 10]) are shown to be super-λ Also, the digraph GB∗(n,d) proposed in [25] as a maximally connected d-regular digraph with quasiminimal diameter (at most one larger than the lower bound) is proved to be super-λ for any d>2 and any order n>d3