|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Характеризация хорошо укрытых графов в терминах запрещенных костабильных
подграфов
И. Э. Зверович Белорусский государственный университет
Аннотация:
Граф называется хорошо укрытым, если каждое максимальное независимое множество является наибольшим. Пусть $I$ – независимое множество (возможно, пустое) в графе $G$. Подграф графа $G$, полученный удалением множества $I$ вместе с окрестностью,
называется костабильным. Получена характеризация класса хорошо укрытых графов в терминах минимального множества запрещенных костабильных подграфов. Из нее
вытекают характеризации известных подклассов класса хорошо укрытых графов и существование полиномиального алгоритма распознавания хорошо укрытых графов с ограниченными степенями вершин.
Библиография: 8 названий.
Поступило: 02.12.1997 Исправленный вариант: 15.04.1999
Образец цитирования:
И. Э. Зверович, “Характеризация хорошо укрытых графов в терминах запрещенных костабильных
подграфов”, Матем. заметки, 67:1 (2000), 52–56; Math. Notes, 67:1 (2000), 41–44
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm813https://doi.org/10.4213/mzm813 https://www.mathnet.ru/rus/mzm/v67/i1/p52
|
Статистика просмотров: |
Страница аннотации: | 321 | PDF полного текста: | 203 | Список литературы: | 47 | Первая страница: | 1 |
|