Diameter-vulnerability of large bipartite digraphs (Q1917252)

The \(s\)-diameter-vulnerability of a digraph \(G\) is the maximum of the diameters of the digraphs formed by removing \(s\) arbitrary vertices from \(G\). Among all bipartite digraphs with \(n\) vertices and maximum out-degree \(d\), the paper gives a lower bound for the \(s\)-diameter-vulnerability; and for \(n= 2(d^{D- 1}+ d^{D-3})\) there are bipartite digraphs with \(s\)-diameter-vulnerability at most one larger than this lower bound, where \(D\) is the diameter. An algorithm is given for finding a path of length at most \(D+ 2\) between any pair of vertices even if some vertices are faulty.