Abstract: The degree d(x) of a vertex or face x in a graph G is the number ofincident edges. A face f = v1 vd(f) in a graph G on the plane or other orientable surface is of type (k1; k2; : : :) if d(vi) ki for each i. By we denote the minimum vertex-degree of G. It follows from the classical theorem by Lebesgue (1940) that every plane triangulation with 4 has a 3-face of types (4; 4;1), (4; 5; 19), (4; 6; 11), (4; 7; 9), (5; 5; 9), or (5; 6; 7). In 1999, Jendrol' gave a similar description: \(4; 4;1), (4; 5; 13), (4; 6; 17), (4; 7; 8), (5; 5; 7), (5; 6; 6)" and conjectured that \(4; 4;1), (4; 5; 10), (4; 6; 15), (4; 7; 7), (5; 5; 7), (5; 6; 6)" holds. In 2002, Lebesgue's description was strengthened by Borodin to \(4; 4;1), (4; 5; 17), (4; 6; 11), (4; 7; 8), (5; 5; 8), (5; 6; 6)". In 2014, we obtained the following tight description, which, in particular, disproves the above mentioned conjecture by Jendrol': \(4; 4;1), (4; 5; 11), (4; 6; 10), (4; 7; 7), (5; 5; 7), (5; 6; 6)", and recently proved another tight description of faces in plane triangulations with 4: \(4; 4;1), (4; 6; 10), (4; 7; 7), (5; 5; 8), (5; 6; 7)". It follows from Lebesgue's theorem of 1940 that every plane 3-connected quadrangulation has a face of one of the types (3; 3; 3;1), (3; 3; 4; 11), (3; 3; 5; 7), (3; 4; 4; 5). Recently, we improved this description to \(3; 3; 3;1),(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 the following tight description of the faces of torus quadrangulations with 3: \(3; 3; 3;1), (3; 3;4; 10), (3; 3; 5; 7), (3; 3; 6; 6), (3; 4; 4; 6), (4; 4; 4; 4)". Recently, we proved that every triangulation with 4 of the torus has a face of one of the types (4; 4;1), (4; 6; 12), (4; 8; 8), (5; 5; 8), (5; 6; 7), or (6; 6; 6), which description is tight. The purpose of this paper is to prove that every graph with 4 that admits a closed 2-cell embedding on the torus has a face of one of the types (4; 4; 4; 4), (4; 4;1), (4; 5; 16), (4; 6; 12), (4; 8; 8), (5; 5; 8), (5; 6; 7), or (6; 6; 6), where all parameters are best possible.

Cite: Borodin O.V. , Ivanova A.O.
Tight description of faces in toroidal graphs with minimum degree at least 4
Discussiones Mathematicae - Graph Theory. 2025. V.45. N1. P.239-251. DOI: 10.7151/dmgt.2529 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Jun 7, 2023
Accepted:	Oct 27, 2023
Published online:	Nov 17, 2023
Published print:	Jan 9, 2025

Identifiers:

Web of science:	WOS:001146181100001
Scopus:	2-s2.0-85215413671
Elibrary:	64262795
OpenAlex:	W4388837951

Citing: Пока нет цитирований

Altmetrics: