Asymptotically Optimal \((\Delta, D’, s)\)-Digraphs

A \((\Delta, D’, s)\)-digraph is a digraph with maximum out-degree \(\Delta\) such that after the deletion of any \(s\) of its vertices the resulting digraph has diameter at most \(D’\). Our concern is to find large, i.e. with order as large as possible, \((\Delta, D’, s)\)-digraphs. To this end, new families of digraphs satisfying a Menger-type condition are given. Namely, between any pair of non-adjacent vertices they have \(s + 1\) internally disjoint paths of length at most \(D’\). Then, new families of asymptotically optimal \((\Delta, D’, s)\)-digraphs are obtained.