Дискретная математика и математическая кибернетика
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
Аннотация:
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.
Ключевые слова:
plane graph, torus, triangulation, quadrangulation, structure properties, 3-faces.
УДК:
519.172.2
MSC: 05C75 Поступила 28 октября 2021 г., опубликована
1 декабря 2021 г.
Язык публикации: английский
DOI:
10.33048/semi.2021.18.110