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

Полунесводимый граф (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] является двудольным полунесводимым или несводимым графом.

Литература

• Харари Ф. Теория графов. — М.: Мир, 1973.