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

Аннотация

Рассмотрено понятие графа, критического для условия, что число вершинной независимости равно минимальной размерности ортонормального помечивания и строго меньше наименьшего размера кликового покрытия. Найдены необходимые и достаточные условия того, что граф является критическим в указанном смысле. На основе полученных результатов улучшены достаточные условия для того, чтобы равенство числа вершинной независимости иминимальной размерности ортонормального помечивания графавлекло равенство числа вершинной независимости и минимального размера кликового покрытия. Библиогр. 16 назв. Ил. 1.

Ключевые слова:

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