Authors: O.V. Borodin, M.A. Bykov, A.O. Ivanova Title: Low 5-stars at 5-vertices in 3-polytopes with minimum degree 5 and no vertices of degree from 7 to 9 Source: Discussiones Mathematicae Graph Theory Received 18.12.2017, Revised 25.06.2018, Accepted 25.06.2018, doi: 10.7151/dmgt.2159 | |
Abstract: In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class \bf P_{5} of 3-polytopes with minimum degree 5. Given a 3-polytope P, by h_{5}(P) we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P. Recently, Borodin, Ivanova and Jensen showed that if a polytope P in \bf P_{5} is allowed to have a 5-vertex adjacent to two 5-vertices and two more vertices of degree at most 6, called a (5,5,6,6,∞)-vertex, then h_{5}(P) can be arbitrarily large. Therefore, we consider the subclass \bf P^{*}_{5} of 3-polytopes in \bf P_{5} that avoid (5,5,6,6,∞)-vertices. For each P^{*} in \bf P^{*}_{5} without vertices of degree from 7 to 9, it follows from Lebesgue's Theorem that h_{5}(P^{*})\le 17. Recently, this bound was lowered by Borodin, Ivanova, and Kazak to the sharp bound h_{5}(P^{*})\le 15 assuming the absence of vertices of degree from 7 to 11 in P^{*}. In this note, we extend the bound h_{5}(P^{*})\le 15 to all P^{*}s without vertices of degree from 7 to 9. | |
Keywords: planar map, planar graph, 3-polytope, structural properties, 5-star, weight, height | |
Links: |