Geodesic
$\mathrm{T}$-irreducible extensions for unions of complete graphs
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 5 (2005) no. 1-2, pp. 107-115 
S. G. Kurnosova. $\mathrm{T}$-irreducible extensions for unions of complete graphs. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 5 (2005) no. 1-2, pp. 107-115. http://geodesic.mathdoc.fr/item/ISU_2005_5_1-2_a10/
@article{ISU_2005_5_1-2_a10,
     author = {S. G. Kurnosova},
     title = {$\mathrm{T}$-irreducible extensions for unions of complete graphs},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {107--115},
     year = {2005},
     volume = {5},
     number = {1-2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2005_5_1-2_a10/}
}
TY  - JOUR
AU  - S. G. Kurnosova
TI  - $\mathrm{T}$-irreducible extensions for unions of complete graphs
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2005
SP  - 107
EP  - 115
VL  - 5
IS  - 1-2
UR  - http://geodesic.mathdoc.fr/item/ISU_2005_5_1-2_a10/
LA  - ru
ID  - ISU_2005_5_1-2_a10
ER  - 
%0 Journal Article
%A S. G. Kurnosova
%T $\mathrm{T}$-irreducible extensions for unions of complete graphs
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2005
%P 107-115
%V 5
%N 1-2
%U http://geodesic.mathdoc.fr/item/ISU_2005_5_1-2_a10/
%G ru
%F ISU_2005_5_1-2_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

$\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.

[1] Avizhenis A., “Otkazoustoichivost — svoistvo, obespechivayuschee postoyannuyu rabotosposobnost tsifrovykh sistem”, Tr. In-ta inzhenerov po elektrotekhnike i radioelektronike, 66:1O (1978), 5–25 | MR

[2] Hayes P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., S-25:9 (1976), 875–884 | DOI | MR | Zbl

[3] Salii V. N., “Dokazatelstva s nulevym razglasheniem v zadachakh o rasshireniyakh grafov”, Vestn. Tomsk. un-ta, 2003, no. 6, Pril., 63–65 | MR

[4] Kurnosova S. G., T-neprivodimye rasshireniya 3-, 4-, 5- i 6-vershinnykh grafov, Dep. v VINITI 21.06.2003, No 1203-B2003, Saratov, 2003, 18 pp.

[5] Kurnosova S. G., “T-neprivodimye rasshireniya dlya nekotorykh klassov grafov”, Teoreticheskie problemy informatiki i ee prilozhenii, 6, Saratov, 2005

[6] Kurnosova S. G., Katalog T-neprivodimykh rasshirenii dlya derevev s chislom vershin ne bolee 1O, Dep. v VINITI 30.06.2004, No 1126-82004, Saratov, 2004, 16 pp.

[7] Kurnosova S. G., “T-neprivodimye rasshireniya bespovtornykh ob'edinenii polnykh grafov”, Molodezh. Obrazovanie. Ekonomika, Sb. nauch. st., v. 4, Yaroslavl, 2004, 289–292 | MR

[8] Onlain-entsiklopediya tselochislennykh posledovatelnostei, posledovatelnost nomer AO00931, http://www.research.att.com/ñjas/sequences