RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2000, том 67, выпуск 1, страницы 52–56 (Mi mzm813)

Эта публикация цитируется в 4 статьях

Характеризация хорошо укрытых графов в терминах запрещенных костабильных подграфов

И. Э. Зверович

Белорусский государственный университет

Аннотация: Граф называется хорошо укрытым, если каждое максимальное независимое множество является наибольшим. Пусть $I$ – независимое множество (возможно, пустое) в графе $G$. Подграф графа $G$, полученный удалением множества $I$ вместе с окрестностью, называется костабильным. Получена характеризация класса хорошо укрытых графов в терминах минимального множества запрещенных костабильных подграфов. Из нее вытекают характеризации известных подклассов класса хорошо укрытых графов и существование полиномиального алгоритма распознавания хорошо укрытых графов с ограниченными степенями вершин.
Библиография: 8 названий.

УДК: 519.1

Поступило: 02.12.1997
Исправленный вариант: 15.04.1999

DOI: 10.4213/mzm813


 Англоязычная версия: Mathematical Notes, 2000, 67:1, 41–44

Реферативные базы данных:


© МИАН, 2024