RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления // Архив

Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2014, выпуск 1, страницы 90–103 (Mi vspui173)

Прикладная математика

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

Е. В. Просолупов

Санкт-Петербургский государственный университет, 199034, Санкт-Петербург, Российская Федерация

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

Ключевые слова: граф, ортонормальное помечивание, ранг, минимальный ранг, симметричные матрицы, клика, независимое множество, минимальный размер кликового покрытия, число вершинной независимости, минимальная размерность ортонормального помечивания.

УДК: 519.17

Поступила: 31 октября 2013 г.



© МИАН, 2024