|
Discrete mathematics and mathematical cybernetics
Tight description of faces in torus triangulations with minimum degree 5
O. V. Borodina, A. O. Ivanovab a Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
b Ammosov North-Eastern Federal University, 48, Kulakovskogo str., Yakutsk, 677013, Russia
Abstract:
The degree $d$ of a vertex or face in a graph $G$ is the number of incident edges. A face $f=v_1\ldots v_{d}$ in a plane or torus graph $G$ is of type $(k_1,k_2,\ldots, k_d)$ if $d(v_i)\le k_i$ for each $i$. By $\delta$ we denote the minimum vertex-degree of $G$. In 1989, Borodin confirmed Kotzig's conjecture of 1963 that every plane graph with minimum degree $\delta$ equal to 5 has a $(5,5,7)$-face or a $(5,6,6)$-face, where all parameters are tight. It follows from the classical theorem of Lebesgue (1940) that every plane quadrangulation with $\delta\ge3$ has a face of one of the types $(3,3,3,\infty)$, $(3,3,4,11)$, $(3,3,5,7)$, $(3,4,4,5)$. Recently, we improved this description to the following one: "$(3,3,3,\infty)$, $(3,3,4,9)$, $(3,3,5,6)$, $(3,4,4,5)$", where all parameters except possibly $9$ are best possible and 9 cannot go down below 8. In 1995, Avgustinovich and Borodin proved that every torus quadrangulation with $\delta\ge3$ has a face of one of the following types: $(3,3,3,\infty)$, $(3, 3, 4, 10)$, $(3, 3, 5, 7)$, $(3, 3, 6, 6)$, $(3, 4, 4, 6)$, $(4, 4, 4, 4)$, where all parameters are best possible. The purpose of our note is to prove that every torus triangulation with $\delta\ge5$ has a face of one of the types $(5,5,8)$, $(5,6,7)$, or $(6,6,6)$, where all parameters are best possible.
Keywords:
plane graph, torus, triangulation, quadrangulation, structure properties, 3-faces.
Received October 28, 2021, published December 1, 2021
Citation:
O. V. Borodin, A. O. Ivanova, “Tight description of faces in torus triangulations with minimum degree 5”, Sib. Èlektron. Mat. Izv., 18:2 (2021), 1475–1481
Linking options:
https://www.mathnet.ru/eng/semr1454 https://www.mathnet.ru/eng/semr/v18/i2/p1475
|
|