Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

The Degree-Diameter Problem for Outerplanar Graphs

Peter DankelmannElizabeth JonckTomáš Vetrík — 2017

Discussiones Mathematicae Graph Theory

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 Δ , D = Δ D 2 + O Δ D 2 - 1 is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) 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.

Page 1

Download Results (CSV)