The Least Possible Diameter for Cn + 3e

摘要

Let C(n,t) denote the minimal diameter of the altered graphs obtained by adding t edges to the cycle Cn. Chung and Garey (J. Graph Theory, 8(1984), 511-534) proved that for all n ≥ 5, n/(t+2)-1≤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.