Geodesic
On minimal vertex 1-extensions of special type graph union
Prikladnaâ diskretnaâ matematika, no. 4 (2011), pp. 34-41.

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

In 2001, it was conjectured that the minimal vertex 1-extension of a graph $G+G^*$, where $G^*$ is a minimal vertex 1-extension of graph $G$, is unique up to isomorphism and has the form $G^*+G^*$. We construct two counterexamples to this conjecture showing that, in general, it is wrong. Also, we show that the statement is true for many graphs.
Keywords: graph, minimal vertex extension, exact vertex extension, fault tolerance. 
@article{PDM_2011_4_a4,
     author = {M. B. Abrosimov},
     title = {On minimal vertex 1-extensions of special type graph union},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {34--41},
     publisher = {mathdoc},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_4_a4/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - On minimal vertex 1-extensions of special type graph union
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 34
EP  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_4_a4/
LA  - ru
ID  - PDM_2011_4_a4
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T On minimal vertex 1-extensions of special type graph union
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 34-41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_4_a4/
%G ru
%F PDM_2011_4_a4
M. B. Abrosimov. On minimal vertex 1-extensions of special type graph union. Prikladnaâ diskretnaâ matematika, no. 4 (2011), pp. 34-41. http://geodesic.mathdoc.fr/item/PDM_2011_4_a4/

[1] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, M. Nauka, 1997 | MR | Zbl

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

[3] Abrosimov M. B., “O slozhnosti nekotorykh zadach, svyazannykh s rasshireniyami grafov”, Matem. zametki, 88:5 (2010), 643–650 | Zbl

[4] Abrosimov M. B., “Minimalnye $k$-rasshireniya predpolnykh grafov”, Izv. vuzov. Matematika, 2003, no. 6(493), 3–11 | MR | Zbl

[5] Harary F., Hayes J. P., “Node fault tolerance in graphs”, Networks, 27 (1996), 19–23 | 3.0.CO;2-H class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[6] Abrosimov M. B., “Minimalnye rasshireniya dopolnenii grafov”, Teoreticheskie zadachi informatiki i ee prilozhenii, 4, Izd-vo Sarat. un-ta, Saratov, 2001, 11–19

[7] Abrosimov M. B., Minimalnye rasshireniya grafov, avtoref. dis. $\dots$ kand. fiz.-mat. nauk, SGU, Saratov, 2001, 16 pp.

[8] Abrosimov M. B., Minimalnye vershinnye rasshireniya 4-, 5-, 6- i 7-vershinnykh grafov, Dep. v VINITI 06.09.2000, No 2352 V00, SGU, Saratov, 2000, 26 pp.