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

Сиб. электрон. матем. изв., 2024, том 21, выпуск 1, страницы 495–500 (Mi semr1698)

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

Describing edges in normal plane maps having no adjacent $3$-faces

O. V. Borodina, A. O. Ivanovab

a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Ammosov North-Eastern Federal University, st. Kulakovskogo, 48, 677013, Yakutsk, Russia

Аннотация: The weight $w(e)$ of an edge $e$ in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge $e=uv$ is an $(i,j)$-edge if $d(u)\le i$ and $d(v)\le j$. In 1940, Lebesgue proved that every NPM has a $(3,11)$-edge, or $(4,7)$-edge, or $(5,6)$-edge, where 7 and 6 are best possible. In 1955, Kotzig proved that every $3$-polytope has an edge $e$ with $w(e)\le13$, which bound is sharp. Borodin (1987), answering Erdős' question, proved that every NPM has such an edge. Moreover, Borodin (1991) refined this by proving that there is either a $(3,10)$-edge, or $(4,7)$-edge, or $(5,6)$-edge.
Given an NPM, we observe some upper bounds on the minimum weight of all its edges, denoted by $w$, of those incident with a $3$-face, $w^*$, and those incident with two $3$-faces, $w^{**}$. In particular, Borodin (1996) proved that if $w^{**}=\infty$, that is if an NPM has no edges incident with two $3$-faces, then either $w^*\le9$ or $w\le8$, where both bounds are sharp. The purpose of our note is to refine this result by proving that in fact $w^{**}=\infty$ implies either a $(3,6)$- or $(4,4)$-edge incident with a $3$-face, or a $(3,5)$-edge, which description is tight.

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

УДК: 519.172.2

MSC: 05C75

Поступила 14 ноября 2023 г., опубликована 23 июня 2024 г.

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

DOI: doi.org/10.33048/semi.2024.21.035



© МИАН, 2024