Дискретная математика и математическая кибернетика
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