Authors:
O.V. Borodin, A.O. Ivanova, E.I. Vasil'eva
Title:
Light minor 5-stars in 3-polytopes with minimum degree 5 and no 6-vertices
Source:
Discussiones Mathematicae Graph Theory
Received 30.11.2017, Revised 11.06.2018, Accepted 12.06.2018, doi: 10.7151/dmgt.2155

Abstract:
In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class \bf P5 of 3-polytopes with minimum degree 5. Given a 3-polytope P, by w(P) denote the minimum of the degree-sum (weight) of the neighborhoods of 5-vertices (minor 5-stars) in P. In 1996, Jendrol' and Madaras showed that if a polytope P in \bf P5 is allowed to have a 5-vertex adjacent to four 5-vertices, then w(P) can be arbitrarily large. For each P in \bf P5 without vertices of degree 6 and 5-vertices adjacent to four 5-vertices, it follows from Lebesgue's Theorem that w(P)\le 68. Recently, this bound was lowered to w(P)\le 55 by Borodin, Ivanova, and Jensen and then to w(P)\le 51 by Borodin and Ivanova. In this note, we prove that every such polytope P satisfies w(P)\le 44, which bound is sharp.
Keywords:
planar map, planar graph, 3-polytope, structural properties, 5-star, weight, height

Links:
PDF