The degree-diameter problem for outerplanar graphs

For positive integers Δ and D we define nΔ,D to be the largest num- ber of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that nΔ,D = Δ D/2 + O ( Δ D/2-1 ) if D is even, and nΔ,D = 3Δ D-1/2 + O ( Δ D-1/2 -1 ) if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of ver- tices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.