|
This article is cited in 7 scientific papers (total in 7 papers)
Discrete mathematics and mathematical cybernetics
Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$
O. V. Borodina, A. O. Ivanovab a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, str. Kulakovskogo, 48,
677000, Yakutsk, Russia
Abstract:
In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of $5$-vertices in the class $\mathbf{P}_5$ of $3$-polytopes with minimum degree $5$.
Given a $3$-polytope $P$, by $w(P)$ ($h(P)$) we denote the minimum degree-sum (minimum of the maximum degrees) of the neighborhoods of $5$-vertices in $P$.
A $5^*$-vertex is a $5$-vertex adjacent to four $5$-vertices. It is known that if a polytope $P$ in $\mathbf{P}_5$ has a $5^*$-vertex, then $h(P)$ can be arbitrarily large.
For each $P$ without vertices of degrees from $6$ to $9$ and $5^*$-vertices in $\mathbf{P}_5$, it follows from Lebesgue's Theorem that $w(P)\le 44$ and $h(P)\le 14$.
In this paper, we prove that every such polytope $P$ satisfies $w(P)\le 42$ and $h(P)\le 12$, where both bounds are tight.
Keywords:
planar map, planar graph, $3$-polytope, structural properties, height, weight.
Received May 18, 2016, published June 30, 2016
Citation:
O. V. Borodin, A. O. Ivanova, “Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$”, Sib. Èlektron. Mat. Izv., 13 (2016), 584–591
Linking options:
https://www.mathnet.ru/eng/semr695 https://www.mathnet.ru/eng/semr/v13/p584
|
Statistics & downloads: |
Abstract page: | 210 | Full-text PDF : | 47 | References: | 45 |
|