Полунесводимый граф

Полунесводимый граф (Semiirreducible graph) - двудольный граф с [math]\displaystyle{ V = S \cup T }[/math], имеющий точно одно наименьшее вершинное покрытие [math]\displaystyle{ M }[/math], причем или [math]\displaystyle{ M \cap S }[/math], или [math]\displaystyle{ M \cap T }[/math] пусто.

Верна теорема Харари и Пламмера: Граф [math]\displaystyle{ G }[/math] и его реберное ядро [math]\displaystyle{ C_{1}(G) }[/math] совпадают тогда и только тогда, когда [math]\displaystyle{ G }[/math] является двудольным полунесводимым или несводимым графом.

Литература

[Харари]