The Degree-Diameter Problem for Outerplanar Graphs

摘要

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 = Δ D 2 + O ? ( Δ D 2 ? 1 ) 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 vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals n _(Δ, D ).