$1$-Треугольные графы и совершенные окрестностные множества

Граф называется $1$-треугольным, если для любого максимального независимого множества $I$ этого графа каждое ребро графа, оба конца которого не принадлежат $I$, содержится ровно в одном треугольнике с вершиной из множества $I$. Получена характеризация $1$-треугольных графов, из которой следует полиномиальный алгоритм их распознавания. Установлена сложность вычисления в классе $1$-треугольных графов ряда теоретико-графовых параметров, связанных с независимостью и доминированием. В частности, установлена $\mathrm{NP}$-полнота задачи о наименьшем совершенном окрестностном множестве в классе всех графов. Библиогр. 20.