The Degree-Diameter Problem for Outerplanar Graphs

Abstract

For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that nΔ,D=ΔD2+O (ΔD2−1)$n_{\Delta ,D} = \Delta ^{{D \over 2}} + O\left( {\Delta ^{{D \over 2} - 1} } \right)$ is even, and nΔ,D=3ΔD−12+O (ΔD−12−1)$n_{\Delta ,D} = 3\Delta ^{{{D - 1} \over 2}} + O\left( {\Delta ^{{{D - 1} \over 2} - 1} } \right)$ if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.

Keywords

• outerplanar
• diameter
• degree
• degree-diameter problem
• distance
• separator theorem
• 05c35
• 05c12