О достаточных условиях равенства числа вершинной независимости и минимального размера кликового покрытия для одного класса графов

Для обыкновенного графа улучшены достаточные условия для того, чтобы равенство числа вершинной независимости и минимальной размерности ортонормального помечивания графа влекло равенство числа вершинной независимости и минимального размера кликового покрытия. Для формулировки этого условия рассмотрен класс графов, имеющих определенную структуру. Пусть $W$ — граф «колесо» с нечетным количеством вершин $n\geq 5$. Удалим каждое второе ребро от центральной вершины графа. Таким образом будет получена структура, состоящая из последовательности циклов $C_4$ без ребер с общей вершиной и общим ребром для каждой последовательной пары циклов. Исследованы некоторые свойства такой структуры. Доказано, что каждый граф $H$, для которого выполняется $\alpha(H) = d(H) < \overline\chi(H)$, содержит указанную структуру. Значит, если для некоторого графа число вершинной независимости равно минимальной размерности ортонормального помечивания графа $G$ и граф $G$ не содержит описанной структуры, то число вершинной независимости графа $G$ равно минимальному размеру кликового покрытия графа $G$. Рассмотрена степень улучшения условий в сравнении с ранее известными условиями. Библиогр. 17 назв. Ил. 10.