THE DIAMETER and RADIUS of RADIALLY MAXIMAL GRAPHS

A graph is called radially maximal if it is not complete and the addition of any new edge decreases its radius. Harary and Thomassen ['Anticritical graphs', Math. Proc. Cambridge Philos. Soc. 79(1) (1976), 11-18] proved that the radius r and diameter d of any radially maximal graph satisfy r ≤ d ≤ 2r - 2. Dutton et al. ['Changing and unchanging of the radius of a graph', Linear Algebra Appl. 217 (1995), 67-82] rediscovered this result with a different proof and conjectured that the converse is true, that is, if r and d are positive integers satisfying r ≤ d ≤ 2r - 2, then there exists a radially maximal graph with radius r and diameter d. We prove this conjecture and a little more.