11.3.2. Доминирование и независимость

Доминирование тесно связано с вершинной независимостью.

ТЕОРЕМА Независимое множество вершин является максимальным тогда и только тогда, когда оно является доминирующим.

доказательство

Необходимость. Пусть множество вершин 5 (5 с V) — максимальное незави­симое. Допустим (от противного), что оно не доминирующее. Тогда существует вершина v, находящаяся на расстоянии больше 1 от всех вершин множества S.

Эту вершину можно добавить к S с сохранением независимости, что противоре­чит максимальности.

Достаточность. Пусть S — независимое доминирующее множество. Допустим (от противного), что оно не максимальное. Тогда существует вершина v, не смежная ни с одной из вершин множества 5, то есть находящаяся на расстоянии боль­ ше 1 от всех вершин множества S. Это противоречит тому, что множество S — доминирующее.

Независимое доминирующее множество вершин называется ядром графа.