Tight description of faces in toroidal graphs with minimum degree at least 4 Научная публикация
Журнал |
Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892 |
||||
---|---|---|---|---|---|
Вых. Данные | Год: 2025, Том: 45, Номер: 1, Страницы: 239-251 Страниц : 13 DOI: 10.7151/dmgt.2529 | ||||
Ключевые слова | plane graph, toroidal graph, degree, face, structure. | ||||
Авторы |
|
||||
Организации |
|
Информация о финансировании (1)
1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0017 |
Реферат:
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.
Библиографическая ссылка:
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
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
Даты:
Поступила в редакцию: | 7 июн. 2023 г. |
Принята к публикации: | 27 окт. 2023 г. |
Опубликована online: | 17 нояб. 2023 г. |
Опубликована в печати: | 9 янв. 2025 г. |
Идентификаторы БД:
Web of science: | WOS:001146181100001 |
Scopus: | 2-s2.0-85215413671 |
РИНЦ: | 64262795 |
OpenAlex: | W4388837951 |
Цитирование в БД:
Пока нет цитирований