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
Cet article a éte moissonné depuis 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},
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
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