The least possible diameter for Cn+ 3e

Abstract

Let C(n, t) denote the minimal diameter of the altered graphs obtained by adding t edges to the cycle C_n. Chung and Garey (J. Graph Theory, 8(1984), 511-534) proved that for all n ≥ 5, n/t+2-l ≤ C(n, t) < n/t+2+3 for even t and n/t+1-1 ≤ C(n, t) < n/t+1+3 for odd t. Schoone et al. (J. Graph Theory, 11(1987), 409-427) proved that for all n ≥ 5, C(n, 2) = [n+2/4]. In this paper, we prove that C(n, 3) = [n/4] for n ≥ 9.