Geodesic
Characterization of graphs with a~small number of additional arcs in a~minimal $1$-vertex extension
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 13 (2013) no. 2, pp. 3-9.

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

A graph $G^*$ is a $k$-vertex extension of a graph $G$ if every graph obtained from $G^*$ by removing any $k$ vertices contains $G$. $k$-vertex extension of a graph $G$ with $n+k$ vertices is called minimal if among all $k$-vertex extensions of $G$ with $n+k$ vertices it has the minimal possible number of arcs. We study directed graphs, whose minimal vertex $1$-extensions have a specific number of additional arcs. A solution is given when the number of additional arcs equals one or two. 
@article{ISU_2013_13_2_a0,
     author = {M. B. Abrosimov and O. V. Modenova},
     title = {Characterization of graphs with a~small number of additional arcs in a~minimal $1$-vertex extension},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {3--9},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a0/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - O. V. Modenova
TI  - Characterization of graphs with a~small number of additional arcs in a~minimal $1$-vertex extension
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2013
SP  - 3
EP  - 9
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a0/
LA  - ru
ID  - ISU_2013_13_2_a0
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A O. V. Modenova
%T Characterization of graphs with a~small number of additional arcs in a~minimal $1$-vertex extension
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2013
%P 3-9
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a0/
%G ru
%F ISU_2013_13_2_a0
M. B. Abrosimov; O. V. Modenova. Characterization of graphs with a~small number of additional arcs in a~minimal $1$-vertex extension. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 13 (2013) no. 2, pp. 3-9. http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a0/

[1] Abrosimov M. B., Graph models of fault tolerance, Saratov Univ. Press, Saratov, 2012, 192 pp.

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

[3] Abrosimov M. B., “On the Complexity of Some Problems Related to Graph Extensions”, Math. Notes, 88:5 (2010), 619–625 | DOI | DOI | MR | Zbl

[4] Abrosimov M. B., “Characterization of graphs with a given number of additional edges in a minimal 1-vertex extension”, Applied Discrete Mathematics, 2012, no. 1, 111–120

[5] Abrosimov M. B., “Minimal vertex extensions of directed stars”, Diskr. Mat., 23:2 (2011), 93–102 (in Russian) | DOI | MR