Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 13 (2013) no. 2, pp. 3-9
Citer cet article
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/
@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},
year = {2013},
volume = {13},
number = {2},
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
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
%U http://geodesic.mathdoc.fr/item/ISU_2013_13_2_a0/
%G ru
%F ISU_2013_13_2_a0
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.
[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
