Abstract:$\mathrm{T}$-irreducible extension is îne of kinds of optimal extensions of
graphs. Constructions of optimal extensions are used in diagnosis
of discrete systems ànd in cryptography.
A graph $H$ with $n+1$ vertices is called àn extension of à graph $G$
with $n$ vertices if $G$ can be embedded in every maximal subgraph
of $H$. Any graph $G$ has the trivial extension that is the join $G+v$ of $G$
with some outer vertex $v$. $\mathrm{T}$-irreducible extensions are obtained
from the trivial extension bó removal of maximal number of edges
in such à way that the extension property is preserved.
The problem of finding of the initial graph from ànó of its $\mathrm{T}$-irreducible
extensions has à linear complexity, but until nîw there is nî efficient
algorithm for finding of all $\mathrm{T}$-irreducible extensions of à given graph.
Graphs studied in this paper are unions of complete graphs each
of which has more than îne vertex. An algorithm of construction of
all $\mathrm{T}$-irreducible extensions for such graphs is presented. Also an
estimate of à total amount of the resultihg extensions is made.