ОПИСАНИЕ ГРАНЕЙ В 3–МНОГОГРАННИКАХ БЕЗ ВЕРШИН СТЕПЕНЕЙ ОТ 4 ДО 9
Аннотация
В 1940 г. Лебег доказал, что в каждой нормальной плоской карте найдется грань, набор степеней инцидентных вершин которой мажорируется одной из следующих последовательностей: (3,6,∞), (3,7,41), (3,8,23), (3,9,17), (3,10,14), (3,11,13), (4,4,∞), (4,5,19), (4,6,11), (4,7,9), (5,5,9), (5,6,7), (3,3,3,∞), (3,3,4,11), (3,3,5,7), (3,4,4,5), (3,3,3,3,5).
В данной заметке доказывается, что в каждом 3-многограннике, не содержащем вершины степеней от 4 до 9, найдется грань, набор степеней инцидентных вершин которой мажорируется одной из следующих последовательностей: (3,3,∞), (3,10,12), (3,3,3,∞), (3,3,3,3,3), где все параметры точны.
При поддержке: Работа выполнена в рамках государственной работы «Организация проведения научных исследований» и поддержана Российским фондом фундаментальных исследований (коды проектов 15–01–05867 и 16–01–00499).
Об авторе
А. О. Иванова
Северо-Восточный федеральный университет имени М. К. Аммосова
Россия
Россия
Иванова Анна Олеговна
Северо-Восточный федеральный университет имени М. К. Аммосова, ул. Кулаковского, 48, Якутск 677000
Список литературы
1. Lebesgue H. Quelques cons´equences simples de la formule d’Euler // J. Math. Pures Appl 1940. V. 19. P. 27–43.
2. Borodin O. V. Colorings of plane graphs: a survey // Discrete Math 2013. V. 313, N 4. P. 517–539.
3. Ore O., Plummer M. D. Cyclic coloration of plane graphs // Recent progress in combinatorics (W. T. Tutte, ed.). New York: Acad. Press, 1969. P. 287–293.
4. Plummer M. D., Toft B. Cyclic coloration of 3-polytopes // J. Graph Theory. 1987. V. 11.P. 507–515.
5. Kotzig A. From the theory of Eulerian polyhedra (Russian) // Mat. Casˇ 1963. V. 13. P. 20–31.
6. Бородин О. В. Решение задач Коцига и Грюнбаума об отделимости цикла в плоском графе // Maт. заметки. 1989. V. 46, N 5. P. 9–12.
7. Gru¨nbaum B. Polytopal graphs // Studies in graph theory (D. R. Fulkerson, ed.). 1975.P.201–224. (MAA Stud. Math.; V. 12).
8. Plummer M. D. On the cyclic connectivity of planar graph // Graph theory and application. Berlin: Springer-Verl., 1972. P. 235–242.
9. Steinitz E. Polyeder und Raumeinteilungen // Enzykl. math. Wiss. (Geometrie), 3AB. 1922. V. 12. P. 1–139.
10. Kotzig A. Extremal polyhedral graphs // Ann. New York Acad. Sci 1979. V. 319. P. 569–570. 11. Бородин О. В. Минимальный вес грани в плоских триангуляциях без 4-вершин // Мат. заметки. 1992. Т. 51, № 1. С. 16–19.
11. Borodin O. V. Triangulated 3-polytopes with restricted minimal weight of faces // Discrete Math 1998. V. 186. P. 281–285.
12. Hornˇa´k M., Jendrol’ S. Unavoidable sets of face types for planar maps // Discuss. Math. Graph Theory. 1996. V. 16, N 2. P. 123–142.
13. Бородин О. В., Вудал Д. Р. Вес граней в плоских картах // Maт. заметки. 1998. V. 6, N 5. P. 648–657.
14. Августинович С. В., Бородин О. В. Окрестности ребер в нормальных картах // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 3. С. 3–9.
15. Jendrol’ S., Voss H.-J. Light subgraphs of graphs embedded in the plane – a survey // Discrete Math 2013. V. 313, N 4. P. 406–421.
16. Бородин О. В. Совместное обобщение теорем Лебега и Коцига о комбинаторике плоских графов // Дискрет. математика. 1991. Т. 3, № 4. С. 24–27.
17. Бородин О. В., Лопарев Д. В. Высота младших граней в плоских нормальных картах // Дискрет. анализ и исслед. опеpаций. 1998. Т. 5, № 4. С. 6–17.
18. Ferencova´ B., Madaras T. On the structure of polyhedral graphs with prescribed edge and dual edge weight // Acta Univ. M. Belii Math 2005. V. 12. P. 13–18.
19. Ferencova´ B., Madaras T. Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight // Discrete Math 2010. V. 310. P. 1661–1675.
20. Jendrol’ S. Triangles with restricted degrees of their boundary vertices in plane triangulations // Discrete Math 1999. V. 196. P. 177–196.
21. Madaras T., Sota´k R. The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five // Tatra Mt. Math. Publ 1999. V. 18. P. 35–56.
22. Madaras T., Skrekovski R., Voss H.-J.ˇ The 7-cycle C7 is light in the family of planar graphs with minimum degree 5 // Discrete Math 2007. V. 307. P. 1430–1435.
23. Mohar B., Skrekovski R., Voss H.-J.ˇ Light subraphs in planar graphs of minimum degree 4 and edge-degree 9 // J. Graph Theory. 2003. V. 44. P. 261–295.
24. Madaras T., Skrekovski R.ˇHeavy paths, light stars, and big melons // Discrete Math 2004.V. 286. P. 115–131.
25. Бородин О. В. Усиление теоремы Лебега о строении младших граней в выпуклых многогранниках // Дискрет. анализ и исслед. операций. 2002. Т. 9, № 3. С. 29–39.
26. Borodin O. V., Ivanova A. O. Describing 3-faces in normal plane maps with minimum degree 4 // Discrete Math 2013. V. 313, N 23. P. 2841–2847.
27. Borodin O. V., Woodall D. R. Cyclic degrees of 3-polytopes // Graphs Comb 1999. V. 15. P. 267–277.
28. Kotzig A. Contribution to the theory of Eulerian polyhedra // Mat.-Fyz. Casˇ 1955. V. 5. P. 101–113.
29. Wernicke P. Uber den kartographischen Vierfarbensatz // Math. Ann¨ 1904. V. 58. P. 413–426.
Рецензия
Для цитирования:
Иванова А.О. ОПИСАНИЕ ГРАНЕЙ В 3–МНОГОГРАННИКАХ БЕЗ ВЕРШИН СТЕПЕНЕЙ ОТ 4 ДО 9. Математические заметки СВФУ. 2016;23(3):46-54.
For citation:
Ivanova A.O. DESCRIPTION OF FACES IN 3–POLYTOPES WITHOUT VERTICES OF DEGREE FROM 4 TO 9. Mathematical notes of NEFU. 2016;23(3):46-54. (In Russ.)
Просмотров:
13
JATS XML
Послать статью по эл. почте 