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

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