О сложности определения числа доминированля в моногенных классах графов

Задача “доминирующее множество” (ДМ) состоит в том, чтобы для произвольного графа из заданного класса указать мощность минимального доминирующего множества. В статье исследуется задача ДМ на различных классах графов. Классы описываются при помощи конечного множества запрещенных порожденных подграфов. Выводятся достаточные условия, при помощи которых по виду запрещающего множества можно определить полиномиальную полноту задачи ДМ на соответствующем классе графов. Дается критерий, который позволяет однозначно определять, является задача ДМ полиномиально полной или полиномиально простой на классах графов, которые описываются только одним запрещенным порожденным подграфом.