|
Вестник Санкт-Петербургского университета. Серия 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.
Ключевые слова:
граф, ортонормальное помечивание, ранг, минимальный ранг, симметричные матрицы, клика, независимое множество, минимальный размер кликового покрытия, число вершинной независимости, минимальная размерность ортонормального помечивания.
Поступила: 31 октября 2013 г.
Образец цитирования:
Е. В. Просолупов, “О достаточных условиях равенства числа вершинной независимости и минимального размера кликового покрытия для одного класса графов”, Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2014, № 1, 90–103
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vspui173 https://www.mathnet.ru/rus/vspui/y2014/i1/p90
|
Статистика просмотров: |
Страница аннотации: | 124 | PDF полного текста: | 24 | Список литературы: | 33 | Первая страница: | 10 |
|