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

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 495-500.

Résumé

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.

Détail

Keywords: planar graph, plane map, structure properties, $3$-polytope, weight.