The maximum sum of degrees above a threshold in planar graphs (Q1357746)

Taken over the set of all simple planar graphs \(G\) on \(N\) vertices, \(a_k(n)\) is the minimum number of vertices of degree less than \(k\); \(s_k(n)\) is the maximum of the sum of degrees of all vertices of degree \(\geq k\). In [Planar graphs with few vertices of small degree, Discrete Math. 143, No. 1-3, 47-70 (1995; Zbl 0830.05022)] the present authors completed the determination of \(a_k(n)\) for all \(k\) and sufficiently large \(n\). In the present paper they address the analogous problem for \(s_k(n)\), ascribed to Erdös and Vince. Defining \[ W_k(n)=\left\{\begin{aligned} 3n-12+3\left\lfloor\frac{3n-12}{k-3}\right\rfloor&\quad\text{if}\quad 7\leq k\leq 10,\\ 3n-18+3\left\lfloor\frac{3n-18}{8}\right\rfloor&\quad\text{if}\quad k=11,\\ 2n-16+6\left\lfloor\frac{2n-16}{k-6}\right\rfloor &\quad\text{if}\quad k\geq12,\end{aligned}\right. \] they prove Theorem 2: For positive integers \(k\) there exists an \(m_k\) such that, for all \(n\geq m_k\), \(s_k(n)=6n-12\) if \(k\leq 6\), \(s_k(n)=6n-24\) (respectively \(6n-27\)) if \(k=6\) and \(n\) is even (respectively odd), and \(s_k(n)=W_k(n)\) if \(k\geq7\). This completes results of \textit{D. B. West} and \textit{T. G. Will} [Vertex degrees in planar graphs, DIMACS Ser. Discrete Math. Theor. Comput. Sci. 9, 139-149 (1993; Zbl 0790.05047)] by constructing graphs achieving the bounds for all \(n\geq m_k\), when \(k\leq 11\).