Ядро орграфа

Ядро орграфа (Kernel of a digraph) - множество вершин, являющееся одновременно и независимым, и доминирующим. Каждый орграф, не имеющий контуров нечетной длины, обладает ядром. Орграф $D$ называется (1) квази $KP$-орграфом, если каждый собственный индуцированный подграф в $D$ имеет ядро; (2) ядровым совершенным орграфом или $KP$-орграфом, если каждый индуцированный подграф имеет ядро; (3) критическим ядровым несовершенным орграфом или $CKI$-орграфом, если $D$ --- квази $KP$-орграф и не имеет ядра (Вершинное ядро, Ядро реберное).

Литература

[Лекции]