Low 5-Stars at 5-Vertices in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree from 7 to 9

Borodin, Oleg V. ; Bykov, Mikhail A. ; Ivanova, Anna O.

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 4, pp. 1025-1033

Résumé

In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class 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 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 P_5^∗ of 3-polytopes in P_5 that avoid (5, 5, 6, 6, ∞)-vertices. For each P^∗ in P_5^∗ without vertices of degree from 7 to 9, it follows from Lebesgue’s Theorem that h_5(P^∗) ≤ 17. Recently, this bound was lowered by Borodin, Ivanova, and Kazak to the sharp bound h_5(P^∗) ≤ 15 assuming the absence of vertices of degree from 7 to 11 in P^∗. In this note, we extend the bound h_5(P^∗) ≤ 15 to all P^∗s without vertices of degree from 7 to 9.

Détail

Keywords: planar map, planar graph, 3-polytope, structural properties, 5-star, weight, height