matmessМатематические заметки СВФУMathematical notes of NEFU2411-93262587-876XСеверо-Восточный федеральный университет имени М.К. Аммосоваmatmess-379Research ArticleМАТЕМАТИКАТОЧНОЕ ОПИСАНИЕ 4–ЦЕПЕЙ В 3–МНОГОГРАННИКАХ С МИНИМАЛЬНОЙ СТЕПЕНЬЮ 5TIGHT DESCRIPTION OF 4–PATHS IN 3–POLYTOPES WITH MINIMUM DEGREE 5ИвановаА. О.IvanovaA. O.

Иванова Анна Олеговна

Северо-Восточный федеральный университет им. М. К. Аммосова, ул. Кулаковского, 48, Якутск 677000 

Ivanova Anna Olegovna

Nord-East Federal University, Kulakovskogo st., 48, Yakutsk 677000, Russia 

shmgnanna@mail.ruСеверо-Восточный федеральный университет им. М. К. АммосоваРоссияNord-East Federal UniversityRussian Federation2016230620262314655Copyright © Иванова А.О., 20262026Иванова А.О.Ivanova A.O.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matmess.elpub.ru/jour/article/view/379

В 1922 г. Франклин доказал, что каждый 3-многогранник P5 с минимальной степенью 5 содержит 5-вершину, смежную с двумя вершинами степени не более 6, причем результат неулучшаем. В дальнейшем он был уточнен в нескольких направлениях. В частности, Йендроль и Мадараш (1996) доказали существование 4-цепи, сумма степеней вершин которой не превышает 23. Цель данной заметки — доказать, что каждый P5 содержит (5,6,6,6)-цепь или (5,5,5,7)-цепь, причем результат не улучшаем ни по одному из параметров.

Back in 1922, Franklin proved that every 3-polytope P5 with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol’ and Madaras (1996) ensured a 4-path with the vertex degree-sum at most 23.

The purpose of this note is to prove that every P5 has a (5,6,6,6)-path or (5,5,5,7)path, where all parameters are tight.

плоский графплоская картаструктурные свойства3-многогранник4-цепьplanar graphplane mapstructural properties3-polytope4-pathРабота выполнена в рамках государственной работы «Организация проведения научных исследований» и при финансовой поддержке Российского фонда фундаментальных исследований (коды проектов 15–01–05867, 16–01–00499).ReferencesWernicke P. Uber den kartographischen Vierfarbensatz // Math. Ann. 1904. Bd 58. S. 413–¨ 426.Wernicke P. Uber den kartographischen Vierfarbensatz // Math. Ann. 1904. Bd 58. S. 413–¨ 426.Franklin P. The four color problem // Amer. J. Math 1922. V. 44. P. 225–236.Franklin P. The four color problem // Amer. J. Math 1922. V. 44. P. 225–236.Aksenov V. A., Borodin O. V., Ivanova A. O. Weight of 3-paths in sparse plane graphs // Electron. J. Comb 2015. V. 22, N 3. P. #P3.28.Aksenov V. A., Borodin O. V., Ivanova A. O. Weight of 3-paths in sparse plane graphs // Electron. J. Comb 2015. V. 22, N 3. P. #P3.28.Ando K., Iwasaki S., Kaneko A. Every 3-connected planar graph has a connected subgraph with small degree sum (Japanese) // Annual Meeting of Mathematical Society of Japan. 1993. 5. Бородин О. В. Решение задач Коцига и Грюнбаума об отделимости цикла в плоском графе // Maт. заметки. 1989. V. 46, N 5. P. 9–12.Ando K., Iwasaki S., Kaneko A. Every 3-connected planar graph has a connected subgraph with small degree sum (Japanese) // Annual Meeting of Mathematical Society of Japan. 1993. 5. Бородин О. В. Решение задач Коцига и Грюнбаума об отделимости цикла в плоском графе // Maт. заметки. 1989. V. 46, N 5. P. 9–12.Borodin O. V. Structural properties of plane maps with minimum degree 5 // Math. Nachr 1992. V. 18. P. 109–117.Borodin O. V. Structural properties of plane maps with minimum degree 5 // Math. Nachr 1992. V. 18. P. 109–117.Borodin O. V. Structural theorem on plane graphs with application to the entire coloring // J. Graph Theory. 1996. V. 23, N 3. P. 233–239.Borodin O. V. Structural theorem on plane graphs with application to the entire coloring // J. Graph Theory. 1996. V. 23, N 3. P. 233–239.Borodin O. V. Minimal vertex degree sum of a 3-path in plane maps // Discuss. Math. Graph Theory. 1997. V. 17, N 2. P. 279–284.Borodin O. V. Minimal vertex degree sum of a 3-path in plane maps // Discuss. Math. Graph Theory. 1997. V. 17, N 2. P. 279–284.Borodin O. V., Ivanova A. O. Describing (d − 2)-stars at d-vertices, d ≤ 5, in normal plane maps // Discrete Math 2013. V. 313, N 17. P. 1700–1709.Borodin O. V., Ivanova A. O. Describing (d − 2)-stars at d-vertices, d ≤ 5, in normal plane maps // Discrete Math 2013. V. 313, N 17. P. 1700–1709.Borodin O. V., Ivanova A. O. Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5 // Discrete Math 2013. V. 313, N 17. P. 1710–1714.Borodin O. V., Ivanova A. O. Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5 // Discrete Math 2013. V. 313, N 17. P. 1710–1714.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.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.Бородин О. В., Иванова А. О. Каждый 3-многогранник с минимальной степенью 5 содержит 7-цикл с максимальной степенью вершин не более 15 // Сиб. мат. журн 2015. Т. 56, № 4. С. 775–789.Бородин О. В., Иванова А. О. Каждый 3-многогранник с минимальной степенью 5 содержит 7-цикл с максимальной степенью вершин не более 15 // Сиб. мат. журн 2015. Т. 56, № 4. С. 775–789.Borodin O. V., Ivanova A. O. Describing tight descriptions of 3-paths in triangle-free normal plane maps // Discrete Math 2015. V. 338, N 11. P. 1947–1952.Borodin O. V., Ivanova A. O. Describing tight descriptions of 3-paths in triangle-free normal plane maps // Discrete Math 2015. V. 338, N 11. P. 1947–1952.Borodin O. V., Ivanova A. O., Jensen T. R. 5-Stars of low weight in normal plane maps with minimum degree 5 // Discuss. Math. Graph Theory. 2014. V. 34, N 3. P. 539–546.Borodin O. V., Ivanova A. O., Jensen T. R. 5-Stars of low weight in normal plane maps with minimum degree 5 // Discuss. Math. Graph Theory. 2014. V. 34, N 3. P. 539–546.Borodin O. V., Ivanova A. O., Jensen T. R., Kostochka A. V., Yancey M. P. Describing 3-paths in normal plane maps // Discrete Math 2013. V. 313, N 23. P. 2702–2711.Borodin O. V., Ivanova A. O., Jensen T. R., Kostochka A. V., Yancey M. P. Describing 3-paths in normal plane maps // Discrete Math 2013. V. 313, N 23. P. 2702–2711.Borodin O. V., Ivanova A. O., Kostochka A. V. Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11 // Discrete Math 2014. V. 315–316. P. 128–134.Borodin O. V., Ivanova A. O., Kostochka A. V. Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11 // Discrete Math 2014. V. 315–316. P. 128–134.Borodin O. V., Ivanova A. O., Kostochka A. V. Describing faces in plane triangulations // Discrete Math 2014. V. 319. P. 47–61.Borodin O. V., Ivanova A. O., Kostochka A. V. Describing faces in plane triangulations // Discrete Math 2014. V. 319. P. 47–61.Borodin O. V., Ivanova A. O., Kostochka A. V. Tight descriptions of 3-paths in normal plane maps // J. Graph Theory (accepted).Borodin O. V., Ivanova A. O., Kostochka A. V. Tight descriptions of 3-paths in normal plane maps // J. Graph Theory (accepted).Borodin O. V., Woodall D. R. Short cycles of low weight in normal plane maps with minimum degree 5 // Discuss. Math. Graph Theory. 1998. V. 18, N 2. P. 159–164.Borodin O. V., Woodall D. R. Short cycles of low weight in normal plane maps with minimum degree 5 // Discuss. Math. Graph Theory. 1998. V. 18, N 2. P. 159–164.Ferencova´ B., Madaras T. Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight // Discrete Math 2010. V. 310, N 12. P. 1661–1675.Ferencova´ B., Madaras T. Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight // Discrete Math 2010. V. 310, N 12. P. 1661–1675.Hudak P., Madaras T. On doubly light triangles in plane graphs // Discrete Math 2013. V. 313, N 19. P. 1978–1988.Hudak P., Madaras T. On doubly light triangles in plane graphs // Discrete Math 2013. V. 313, N 19. P. 1978–1988.Jendrol’ S. Paths with restricted degrees of their vertices in planar graphs // Czechoslovak Math. J 1999. V. 49. P. 481–490.Jendrol’ S. Paths with restricted degrees of their vertices in planar graphs // Czechoslovak Math. J 1999. V. 49. P. 481–490.Jendrol’ S. A structural property of convex 3-polytopes // Geom. Dedicata. 1997. V. 68. P. 91–99.Jendrol’ S. A structural property of convex 3-polytopes // Geom. Dedicata. 1997. V. 68. P. 91–99.Jendrol’ S., Madaras T. On light subgraphs in plane graphs with minimum degree five // Discuss. Math. Graph Theory. 1996. V. 16, N 2. P. 207–217.Jendrol’ S., Madaras T. On light subgraphs in plane graphs with minimum degree five // Discuss. Math. Graph Theory. 1996. V. 16, N 2. P. 207–217.Jendrol’ S., Madaras T., Sota´k R., Tuza Z. On light cycles in plane triangulations // Discrete Math 1999. V. 197–198. P. 453–467.Jendrol’ S., Madaras T., Sota´k R., Tuza Z. On light cycles in plane triangulations // Discrete Math 1999. V. 197–198. P. 453–467.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.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.Jendrol’ S., Macekova´ M. Describing short paths in plane graphs of girth at least 5 // Discrete Math 2015. V. 338, N 2. P. 149–158.Jendrol’ S., Macekova´ M. Describing short paths in plane graphs of girth at least 5 // Discrete Math 2015. V. 338, N 2. P. 149–158.Jendrol’ S., Macekova´ M., Sota´k R. Note on 3-paths in plane graphs of girth 4 // Discrete Math 2015. V. 338, N 9. P. 1643–1648.Jendrol’ S., Macekova´ M., Sota´k R. Note on 3-paths in plane graphs of girth 4 // Discrete Math 2015. V. 338, N 9. P. 1643–1648.Lebesgue H. Quelques cons´equences simples de la formule d’Euler // J. Math. Pures Appl 1940. V. 19. P. 27–43.Lebesgue H. Quelques cons´equences simples de la formule d’Euler // J. Math. Pures Appl 1940. V. 19. P. 27–43.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.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.Madaras T. Note on the weight of paths in plane triangulations of minimum degree 4 and 5 // Discuss. Math. Graph Theory. 2000. V. 20, N 2. P. 173–180.Madaras T. Note on the weight of paths in plane triangulations of minimum degree 4 and 5 // Discuss. Math. Graph Theory. 2000. V. 20, N 2. P. 173–180.Madaras T. On the structure of plane graphs of minimum face size 5 // Discuss. Math. Graph Theory. 2004. V. 24, N 3. P. 403–411.Madaras T. On the structure of plane graphs of minimum face size 5 // Discuss. Math. Graph Theory. 2004. V. 24, N 3. P. 403–411.Madaras T. Two variations of Franklin’s theorem // Tatra Mt. Math. Publ 2007. V. 36. P. 61–70.Madaras T. Two variations of Franklin’s theorem // Tatra Mt. Math. Publ 2007. V. 36. P. 61–70.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, N 11–12. P. 1430–1435.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, N 11–12. P. 1430–1435.Mohar B., Skrekovski R., Voss H.-J.ˇ Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9 // J. Graph Theory. 2003. V. 44, N 4. P. 261–295.Mohar B., Skrekovski R., Voss H.-J.ˇ Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9 // J. Graph Theory. 2003. V. 44, N 4. P. 261–295.Borodin O. V., Ivanova A. O. An analogue of Franklin’s Theorem // Discrete Math. 2016. V. 339, N 10. P. 2553–2556.Borodin O. V., Ivanova A. O. An analogue of Franklin’s Theorem // Discrete Math. 2016. V. 339, N 10. P. 2553–2556.Бородин О. В., Иванова А. О. Описание 4-цепей в 3-многогранниках минимальной степени 5 // Сиб. мат. журн. 2016. Т. 57, № 5. С. 981–987.Бородин О. В., Иванова А. О. Описание 4-цепей в 3-многогранниках минимальной степени 5 // Сиб. мат. журн. 2016. Т. 57, № 5. С. 981–987.

The authors declare that there are no conflicts of interest present.