The Degree-Diameter Problem for Outerplanar Graphs

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 -