Decreasing the diameter of cycles

Alon, Gyárfás, and Ruszinkó 1 established a bound for the minimum number of edges that have to be added to a graph of n ≥ n 0 vertices in order to obtain a graph of diameter 2. Alon et al. approximated n 0 by a polynomial function of the maximum degree of the initial graph. They conjectured that the minimum value for n 0 is 12 for the case of C n , as opposed to n 0 = 274 obtained by calculations for the general case. In this paper we prove their conjecture. For the reduction to diameter 3 of a cycle, we also improve the bounds from 1 showing that the minimum number of edges that need to be added to the cycle C n is between n − 59 and n − 8. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 299–303, 2003