| Abstract: | We consider the following problem: Given positive integers k and D, what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D, assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of (k + 1)D and a lower bound of (k + 1)D ? k for even D and of (k + 1)D ? 2k + 2 for odd D ? 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3D ? 1 and 4D ? 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ? 4 and k = 6, and k = 5 and k ? 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√k). For directed graphs G, the bounds depend strongly on D: for D = 1 and D = 2 we derive exact bounds of θ(√k) and of 2k + 2, respectively, while for D ? 3 the resulting diameter is in general unbounded in terms of k and D. Finally, we prove several related problems NP-complete. |
