Logo BSU

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: http://elib.bsu.by/handle/123456789/10807
Заглавие документа: Характеризация хорошо укрытых графов в терминах запрещенных костабильных подграфов
Авторы: Зверович, Игорь Эдмундович
Тема: математика и статистика
Дата публикации: 2000
Библиографическое описание источника: Матем. заметки. - 2000. - Т. 67, № 1. - С. 52–56
Аннотация: Граф называется хорошо укрытым, если каждое максимальное независимое множество является наибольшим. Пусть $I$ – независимое множество (возможно, пустое) в графе $G$. Подграф графа $G$, полученный удалением множества $I$ вместе с окрестностью, называется костабильным. Получена характеризация класса хорошо укрытых графов в терминах минимального множества запрещенных костабильных подграфов. Из нее вытекают характеризации известных подклассов класса хорошо укрытых графов и существование полиномиального алгоритма распознавания хорошо укрытых графов с ограниченными степенями вершин.
URI документа: http://elib.bsu.by/handle/123456789/10807
Располагается в коллекциях:Архив статей механико-математического факультета до 2016 г.



Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.