Графы самопересечений замкнутых ломаных

Abstract

Введен и изучен такой подкласс струнных графов, как графы самопересечений замкнутых ломаных (класс CPC-графов). Указаны необходимые условия принадлежности графа к классу CPC, запрещенные подграфы данного класса, операции над графами, сохраняющие их принадлежность к классу CPC. Рассмотрен вопрос о существовании k-регулярных CPC-графов, в частности найдены пары (k, n) и приведены оценки на количество значений k, при которых существует k-регулярный граф на n вершинах, показано существование бесконечного числа k-регулярных CPC-графов для любого k ∈ . Исследованы алгоритмические вопросы в классе CPC-графов. Доказано, что задачи о доминирующем множестве, раскраске, независимости и наибольшем цикле в классе CPC-графов являются NP-трудными, а задача распознавания CPC-графов принадлежит к классу PSPACE.