@inproceedings{ed7adc81275a4063aaee063a9ecf5e81,
title = "Improved diameter bounds for altered graphs",
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 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.",
author = "A.A. Schoone and Hans Bodlaender and {van Leeuwen}, Jan",
year = "1987",
doi = "10.1007/3-540-17218-1_61",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "227--236",
editor = "Gottfried Tinhofer and Gunther Schmidt",
booktitle = "Proceedings 12th International Workshop on Graph Theoretic Concepts in Computer Science, WG'86",
}