Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000