Open AccessГрафы самопересечений замкнутых ломаных
Author(s) -
Nikolai P. Prochorov,
Ekateri. Dul
Publication year - 2021
Publication title -
žurnal belorusskogo gosudarstvennogo universiteta. matematika, informatika/žurnal belorusskogo gosudarstvennogo universiteta. matematika, informatika
Language(s) - Russian
Resource type - Journals
eISSN - 2617-3956
pISSN - 2520-6508
DOI - 10.33581/2520-6508-2021-1-54-68
Subject(s) - physics , mathematics
Введен и изучен такой подкласс струнных графов, как графы самопересечений замкнутых ломаных (класс CPC-графов). Указаны необходимые условия принадлежности графа к классу CPC, запрещенные подграфы данного класса, операции над графами, сохраняющие их принадлежность к классу CPC. Рассмотрен вопрос о существовании k-регулярных CPC-графов, в частности найдены пары (k, n) и приведены оценки на количество значений k, при которых существует k-регулярный граф на n вершинах, показано существование бесконечного числа k-регулярных CPC-графов для любого k∈N. Исследованы алгоритмические вопросы в классе CPC-графов. Доказано, что задачи о доминирующем множестве, раскраске, независимости и наибольшем цикле в классе CPC графов являются NP-трудными, а задача распознавания CPC-графов принадлежит к классу PSPACE.