# The Degree-Diameter Problem for Outerplanar Graphs

• Volume: 37, Issue: 3, page 823-834
• ISSN: 2083-5892

top

## Abstract

top
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 }^{\frac{D}{2}}+O\left({\Delta }^{\frac{D}{2}-1}\right)$ is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) ${n}_{\Delta ,D}=3{\Delta }^{\frac{D-1}{2}}+O\left({\Delta }^{\frac{D-1}{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.

## How to cite

top

Peter Dankelmann, Elizabeth Jonck, and Tomáš Vetrík. "The Degree-Diameter Problem for Outerplanar Graphs." Discussiones Mathematicae Graph Theory 37.3 (2017): 823-834. <http://eudml.org/doc/288570>.

@article{PeterDankelmann2017,
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.},
author = {Peter Dankelmann, Elizabeth Jonck, Tomáš Vetrík},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {outerplanar; diameter; degree; degree-diameter problem; distance; separator theorem},
language = {eng},
number = {3},
pages = {823-834},
title = {The Degree-Diameter Problem for Outerplanar Graphs},
url = {http://eudml.org/doc/288570},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Peter Dankelmann
AU - Elizabeth Jonck
AU - Tomáš Vetrík
TI - The Degree-Diameter Problem for Outerplanar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 823
EP - 834
AB - 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.
LA - eng
KW - outerplanar; diameter; degree; degree-diameter problem; distance; separator theorem
UR - http://eudml.org/doc/288570
ER -

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.