Diameter vulnerability of graphs

AbstractLet f(t, D) denote the maximum possible diameter of a graph obtained from a (t+1)-edge-connected graph of diameter D by deleting t edges. F.R.K. Chung and M.R. Garey have shown that for D≥4,(t+1)(D−2)≤ f(t, D)≤(t+1)D+t. Here we consider the cases D=2 and D=3 and show that f(t,2)=4 and 32t−3≤f(t,3)≤32t+4 if t is large enough. We solve also the problem for the directed case (answering a question of F.R.K. Chung and M.R. Garey) by showing that if D ≥ 3 the diameter of a diagraph obtained from a (t + 1)-arc-connected digraph of order n by deleting t arcs is at most n−2t+1. In the case D=.....2, the maximum possible diameter of the resulting digraph is (like in the undirected case) 4. We also consider the same problem for vertices