Характеризация наследственных униграфов на основе канонической декомпозиции

Рассматривается класс наследственных униграфов. Граф, определяемый с точностью до изоморфизма списком степеней своих вершин, называется униграфом. Униграф называется наследственным униграфом, если каждый его вершинно порожденный подграф также является униграфом. Известно, что не все униграфы наследственные. В данной работе выполнена характеризация наследственных униграфов на основе теории канонической декомпозиции и предложена схема линейного относительно числа вершин алгоритма распознавания свойства “быть наследственным униграфом”.