Characterization of graphs with a~given number of additional edges in a~minimal 1-vertex extension
Prikladnaâ diskretnaâ matematika, no. 1 (2012), pp. 111-120
Voir la notice de l'article provenant de la source Math-Net.Ru
A graph $G^*$ is $k$-vertex extension of graph $G$ if every graph obtained by removing any $k$ vertices from $G^*$ contains $G$. $k$-Vertex extension of graph $G$ with $n+k$ vertices is called minimal if, among all $k$-vertex extensions of graph $G$ with $n+k$ vertices, it has the minimum possible number of edges. The graphs whose minimal vertex 1-extensions have a specified number of additional edges are studied. A solution is given when the number of additional edges is equal to one, two or three.
Keywords:
graph, minimal vertex extension, exact vertex extension, fault tolerance.
@article{PDM_2012_1_a7,
author = {M. B. Abrosimov},
title = {Characterization of graphs with a~given number of additional edges in a~minimal 1-vertex extension},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {111--120},
publisher = {mathdoc},
number = {1},
year = {2012},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2012_1_a7/}
}
TY - JOUR AU - M. B. Abrosimov TI - Characterization of graphs with a~given number of additional edges in a~minimal 1-vertex extension JO - Prikladnaâ diskretnaâ matematika PY - 2012 SP - 111 EP - 120 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/PDM_2012_1_a7/ LA - ru ID - PDM_2012_1_a7 ER -
M. B. Abrosimov. Characterization of graphs with a~given number of additional edges in a~minimal 1-vertex extension. Prikladnaâ diskretnaâ matematika, no. 1 (2012), pp. 111-120. http://geodesic.mathdoc.fr/item/PDM_2012_1_a7/