Прикладная математика
О достаточных условиях равенства числа вершинной независимости и минимального размера кликового покрытия для одного класса графов
Е. В. Просолупов Санкт-Петербургский государственный университет,
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 г.