Бородин О. В., Иванова А. О.
Каждый 3-многогранник с минимальной степенью 5 содержит 7-цикл с максимальной степенью вершин не более 15

Пусть _φP (C₇) (_φT (C₇)) — минимальное целое k, при котором каждый выпуклый 3-многогранник (соответственно каждая плоская триангуляция) с минимальной степенью 5 содержит 7-цикл, степени всех вершин которого не превышают k. В 1999 г. Йендроль, Мадараш, Сотак и Туза доказали, что 15 ≤ _φT (C₇) ≤ 17. Известно также, что _φP (C₇) ≤ 359 (Мадараш, Шкрековский и Фосс, 2007). В настоящей работе доказано равенство _φP (C₇) = _φT (C₇) = 15, которое является ответом на вопрос Йендроля и др. (1999).

Borodin O. V., Ivanova A. O.
Each 3-polytope with minimum degree 5 has a 7-cycle with maximum degree at most 15

Let _φP (C₇) (_φT (C₇)) be the minimum integer k with the property that each 3-polytope (respectively, each plane triangulation) with minimum degree 5 has a 7-cycle with all vertices of degree at most k. In 1999, Jendrol’, Madaras, Soták, and Tuza proved that 15 ≤ _φT (C₇) ≤ 17. It is also known due to Madaras, Skrekovski, and Voss (2007) that _φP (C₇) ≤ 359.
We prove that _φP (C₇) = _φT (C₇) = 15, which answers a question of Jendrol’ et al. (1999).

DOI 10.17377/smzh.2015.56.405
Ключевые слова: плоский граф, структурные свойства, 3-многогранник, высота.

Полный текст статьи / Full texts:

• PDF file
• PostScript file