Vertex Degrees in Outerplanar Graphs

Abstract

For an outerplanar graph on $n$ vertices, we determine the maximum number of vertices of degree at least $k$. For $k=4$ (and $n\ge 7$) the answer is $n–4$. For $k=5$ (and $n\ge 4$), the answer is $\lfloor \frac{2(n-4)}{3}\rfloor$ (except one less when $n\equiv 1(\mathrm{mod}6)$). For $k\ge 6$ (and $n\ge k+2$), the answer is $\lfloor \frac{n-6}{k-4}\rfloor$. We also determine the maximum sum of the degrees of $s$ vertices in an $n$-vertex outerplanar graph and the maximum sum of the degrees of the vertices with degree at least $k$.