Diameter vulnerability of graphs (Q800372)

Let f(t,D) denote the maximum diameter of a graph obtained from a \((t+1)\)-edge-connected graph of diameter D by deleting t edges. In the paper it is shown that for \(D=2\) and \(D=3\), \(f(t,2)=4\), \(3\sqrt{2t}-3\leq f(t,3)\leq 3\sqrt{2t}+4.\) In the case of a \((t+1)\)-arc-connected digraph of order n and diameter at least 3, the maximum diameter for a digraph obtained from this digraph by deleting t arcs is \(n-2t+1\), and this bound can be achieved. For \(D=2\), the maximum diameter of the resulting digraph is 4.