RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2016, том 13, страницы 584–591 (Mi semr695)

Эта публикация цитируется в 7 статьях

Дискретная математика и математическая кибернетика

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

Аннотация: 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.

Ключевые слова: planar map, planar graph, $3$-polytope, structural properties, height, weight.

Поступила 18 мая 2016 г., опубликована 30 июня 2016 г.

Язык публикации: английский

DOI: 10.17377/semi.2016.13.045



Реферативные базы данных:


© МИАН, 2024