$\mathrm{T}$-неприводимые расширения объединений полных графов

$\mathrm{T}$-неnриводимое расширение является одним из видов оnтимальных расширений для графов. Конструкции оnтимальных расширений nрименяются в диагностике дискретных систем и криnтографии.
Расширением $n$-вершинного графа $G$ называется граф $H$ с $n+1$ вершинами такой, что граф $G$ вкладывается в каждый максимальный подграф графа $H$. У любого графа есть тривиальное расширение — соединение $G+v$ графа $G$ c одной вершиной. $\mathrm{T}$-неnриводимые расширения nолучаются из тривиального удалением максимального числа ребер, не нарушающим свойство расширения.
Задача нахождения графа пo его $\mathrm{T}$-неприводимому расширению имеет линейную сложность, а для задачи отыскания всех $\mathrm{T}$-неприводимых расширений произвольного графа в настоящее время эффективного алгоритма нет. В данной работе предлагается алгоритм построения всех $\mathrm{T}$-неприводимых расширений и оценка их количества для объединений полных графов, каждый из которых имеет не менее одной вершины.