|
Discrete mathematics and mathematical cybernetics
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
Abstract:
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.
Keywords:
planar graph, plane map, structure properties, $3$-polytope, weight.
Received November 14, 2023, published June 23, 2024
Citation:
O. V. Borodin, A. O. Ivanova, “Describing edges in normal plane maps having no adjacent $3$-faces”, Sib. Èlektron. Mat. Izv., 21:1 (2024), 495–500
Linking options:
https://www.mathnet.ru/eng/semr1698 https://www.mathnet.ru/eng/semr/v21/i1/p495
|
|