RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2005 Volume 5, Issue 1-2, Pages 107–115 (Mi isu680)

Computer science

$\mathrm{T}$-irreducible extensions for unions of complete graphs

S. G. Kurnosova

Saratov State University

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.

UDC: 519.17



© Steklov Math. Inst. of RAS, 2025