The Degree-Diameter Problem for Outerplanar Graphs

Peter Dankelmann ; Elizabeth Jonck ; Tomáš Vetrík

Discussiones Mathematicae Graph Theory, Tome 37 (2017), p. 823-834 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2017-01-01
EUDML-ID : urn:eudml:doc:288570