Дискретная математика и Математическая кибернетика
Графы самопересечений замкнутых ломаных
Н. П. Прохоров,
Е. Н. Дуль Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
Аннотация:
Введен и изучен такой подкласс струнных графов, как графы самопересечений замкнутых ломаных (класс
$CPC$-графов). Указаны необходимые условия принадлежности графа к классу
$CPC$, запрещенные подграфы данного класса, операции над графами, сохраняющие их принадлежность к классу
$CPC$. Рассмотрен вопрос о существовании
$k$-регулярных
$CPC$-графов, в частности найдены пары
$(k, n)$ и приведены оценки на количество значений
$k$, при которых существует
$k$-регулярный граф на
$n$ вершинах, показано существование бесконечного числа
$k$-регулярных
$CPC$-графов для любого
$k\in \mathbb{N}$. Исследованы алгоритмические вопросы в классе
$CPC$-графов. Доказано, что задачи о доминирующем множестве, раскраске, независимости и наибольшем цикле в классе
$CPC$-графов являются
$NP$-трудными, а задача распознавания
$CPC$-графов принадлежит к классу
$PSPACE$.
Ключевые слова:
граф пересечений; граф самопересечений замкнутой ломаной; регулярный граф; $NP$-полнота; полиномиальная сводимость.
УДК:
519.172.4+
519.178 Поступила в редакцию: 08.09.2020
DOI:
10.33581/2520-6508-2021-1-54-68