Sciact
  • EN
  • RU

Легкие 3-цепи в 3-многогранниках без смежных 3-граней Научная публикация

Журнал Сибирский математический журнал
ISSN: 0037-4474
Вых. Данные Год: 2024, Том: 65, Номер: 2, Страницы: 249-257 Страниц : 9 DOI: 10.33048/smzh.2024.65.202
Ключевые слова плоский граф, 3-многогранник, разреженный 3-многогранник, структурные свойства, 3-цепь, вес.
Авторы Бородин О.В. 1 , Иванова А.О. 2
Организации
1 Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
2 Северо-Восточный федеральный университет имени М.К. Аммосова, ул. Кулаковского, 48, Якутск 677000

Информация о финансировании (1)

1 Институт математики им. С.Л. Соболева СО РАН FWNF-2022-0017

Реферат: Пусть wk максимум минимальной суммы степеней вершин (веса) в k-вершинных цепях (k-цепях) 3-многогранников. Очевидно, что каждый 3многогранник содержит вершину степени не больше 5, так что w1 ≤ 5. Ещев 1955 г. Коциг доказал, что w2 ≤ 13 (т. е. найдется ребро веса не больше 13), причем оценка точна. В 1993 г. Андо, Ивасаки и Канеко доказали, что w3 ≤ 21, и эта оценка также неулучшаема ввиду конструкции Йендроля, найденной в 1997 г. В 1997 г. О. В. Бородин уточнил этот результат, показав, что w3 ≤ 18 верно для всех 3многогранников с w2 ≥ 7, но для 3-многогранников с w2 ≥ 8 имеет место более сильная оценка w3 ≤ 17, причем неулучшаемость 18 была подтверждена О. В. Бородиным и др. в 2013 г, а неулучшаемость 17 была известна давно. За последние три десятилетия большое число работ было посвящено задачам раскраски и структурным задачам на плоских графах, разреженных в том или ином смысле. В данной статье рассматриваются 3-многогранники без смежных 3-циклов, т. е. не имеющие хордальных 4-циклов (иначе говоря, без K4 − e). Известно, что для таких 3-многогранников w1 ≤ 4 и, более того, w2 ≤ 9, где обе оценки точны (Бородин, 1992). Доказано, что всякий 3-многогранник без хордальных 4-циклов содержит 3-цепь веса не более 15, т. е. w3 ≤ 15, и эта оценка неулучшаема.
Библиографическая ссылка: Бородин О.В. , Иванова А.О.
Легкие 3-цепи в 3-многогранниках без смежных 3-граней
Сибирский математический журнал. 2024. Т.65. №2. С.249-257. DOI: 10.33048/smzh.2024.65.202 РИНЦ
Переводная: Borodin O.V. , Ivanova A.O.
Light 3-Paths in 3-Polytopes without Adjacent Triangles
Siberian Mathematical Journal. 2024. V.65. N2. P.257-264. DOI: 10.1134/S0037446624020022 WOS Scopus РИНЦ РИНЦ OpenAlex
Даты:
Поступила в редакцию: 17 окт. 2023 г.
Принята к публикации: 28 нояб. 2023 г.
Опубликована в печати: 25 мар. 2024 г.
Опубликована online: 25 мар. 2024 г.
Идентификаторы БД:
РИНЦ: 65623353
Цитирование в БД: Пока нет цитирований
Альметрики: