Authors:
O.V. Borodin, A.O. Ivanova, O.N. Kazak
Title:
Describing neighborhoods of 5-vertices in 3-polytopes with minimum degree 5 and without vertices of degrees from 7 to 11
Source:
Discussiones Mathematicae Graph Theory
Received 12.07.2016, Revised 13.01.2017, Accepted 13.01.2017, doi: 10.7151/dmgt.2024

Abstract:
In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: \begin{center} (6,6,7,7,7), (6,6,6,7,9), (6,6,6,6,11),
(5,6,7,7,8), (5,6,6,7,12), (5,6,6,8,10), (5,6,6,6,17),
(5,5,7,7,13), (5,5,7,8,10), (5,5,6,7,27),
(5,5,6,6,∞), (5,5,6,8,15), (5,5,6,9,11),
(5,5,5,7,41), (5,5,5,8,23), (5,5,5,9,17),
(5,5,5,10,14), (5,5,5,11,13). \end{center} In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5,5,6,6,∞), (5,6,6,6,15), (6,6,6,6,6), where all parameters are tight.
Keywords:
planar graph, structure properties, 3-polytope, neighborhood

Links:
PDF