|
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 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.
Citation:
S. G. Kurnosova, “$\mathrm{T}$-irreducible extensions for unions of complete graphs”, Izv. Saratov Univ. Math. Mech. Inform., 5:1-2 (2005), 107–115
Linking options:
https://www.mathnet.ru/eng/isu680 https://www.mathnet.ru/eng/isu/v5/i1/p107
|
|