The maximum sum of degrees above a threshold in planar graphs
type: Item
instance of: scholarly article
title: The maximum sum of degrees above a threshold in planar graphs
zbMATH Open document ID: 0874.05031
DOI: 10.1016/S0012-365X(96)00116-1
author: J. Griggs
author: Yan-Chyuan Lin
published in: Discrete Mathematics
publication date: 1997-10-16T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1021691
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Planar graphs with few vertices of small degree
cites work: The Number of Hexagons and the Simplicity of Geodesics on Certain Polyhedra
cites work: Q3138293
Recommended article: Planar graphs with few vertices of small degree
Recommended article: Q3138293
Recommended article: Small universal graphs for bounded-degree planar graphs
Recommended article: Large planar graphs with given diameter and maximum degree
Recommended article: Q3484851
Recommended article: On vertex-degree restricted subgraphs in polyhedral graphs
Recommended article: On the maximum weight of a planar graph of given order and size
Recommended article: Q3642410
Recommended article: Subgraphs with restricted degrees of their vertices in planar 3-connected graphs
Recommended article: Q4518401
description: scientific article; zbMATH DE number 1021691