RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2021 Volume 18, Issue 2, Pages 1475–1481 (Mi semr1454)

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.

UDC: 519.172.2

MSC: 05C75

Received October 28, 2021, published December 1, 2021

Language: English

DOI: 10.33048/semi.2021.18.110



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024