The Degree-Diameter Problem for Outerplanar Graphs

• Autorzy: Peter Dankelmann , Elizabeth Jonck , Tomáš Vetrík
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

outerplanar; diameter; degree; degree-diameter problem; distance; separator theorem

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 823-834

Daty

wydano

2017-08-01

otrzymano

2016-01-08

poprawiono

2016-08-05

zaakceptowano

2016-08-05

online

2017-07-06

Twórcy

autor

Peter Dankelmann

• , , ,

autor

Elizabeth Jonck

• , , ,

autor

Tomáš Vetrík

• , , ,

Identyfikatory

DOI

10.7151/dmgt.1969