О графах критических для условия на минимальную размерность ортонормального помечивания
Аннотация
Рассмотрено понятие графа, критического для условия, что число вершинной независимости равно минимальной размерности ортонормального помечивания и строго меньше наименьшего размера кликового покрытия. Найдены необходимые и достаточные условия того, что граф является критическим в указанном смысле. На основе полученных результатов улучшены достаточные условия для того, чтобы равенство числа вершинной независимости иминимальной размерности ортонормального помечивания графавлекло равенство числа вершинной независимости и минимального размера кликового покрытия. Библиогр. 16 назв. Ил. 1.Ключевые слова:
граф, критический граф, ортонормальное помечивание, ранг, минимальный ранг, симметричные матрицы, клика, независимое множество, минимальный размер кликового покрытия, число вершинной независимости, минимальная размерность ортонормального помечивания
Скачивания
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.