Asymptotically Optimal $(\mathrm{\Delta },D^{\prime },s)$-Digraphs

Abstract

A $(\mathrm{\Delta },D^{\prime },s)$-digraph is a digraph with maximum out-degree $\mathrm{\Delta }$ such that after the deletion of any $s$ of its vertices the resulting digraph has diameter at most $D^{\prime }$. Our concern is to find large, i.e. with order as large as possible, $(\mathrm{\Delta },D^{\prime },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^{\prime }$. Then, new families of asymptotically optimal $(\mathrm{\Delta },D^{\prime },s)$-digraphs are obtained.