О счётном семействе граничных классов графов для задачи о доминирующем множестве

Наследственный класс  — это множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задаётся множеством своих минимальных запрещённых порождённых подграфов. Если это множество конечно, то класс называется конечно определённым. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определённых классов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, имеется ли в нём такое подмножество вершин заданной мощности, что каждая вершина вне подмножества имеет хотя бы одного соседа в подмножестве. Ранее для данной задачи было известно ровно $4$ граничных класса (если $\mathbb{P}\neq \mathbb{NP}$). В этой работе рассматривается некоторое счётное множество конкретных классов графов и доказывается, что каждый его элемент является граничным классом для задачи о доминирующем множестве (если $\mathbb{P}\neq \mathbb{NP}$). Также доказывается $\mathbb{NP}$-полнота данной задачи для графов, не содержащих порождённого $6$-пути и $4$-клики. Это означает, что множество известных граничных классов для задачи о доминирующем множестве не полное (если $\mathbb{P}\neq \mathbb{NP}$). Библиогр. 11.