Geodesic
Calculation of upper bounds for graph vertex integrity based on the minimal separators
Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 142-144.

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

A vertex integrity of a graph is a generalization of a connectivity notion. It is believed that a graph is more integral if the connectivity of this graph is broken when you delete a larger number of vertices and the effect of these deletions is minimal. Measures of the integrity are introduced to use in the analysis and synthesis of fault-tolerant complex technical systems. One of such measure is a numerical parameter of the graph called the vertex integrity. The evaluation problem for this parameter is NP-hard. Let $G=(V,E)$ be a simple connected graph, $V$ be a set of vertices and $E$ be a set of edges, $n=|V|$. The vertex integrity of $G$ is calculated by the formula $I(G)=\min_{S\subseteq V}\{|S|+w\,(G-S)\}$ where $w(H)$ is the order of the largest connected component of a graph $H$. The minimum value is reached when $S$ is a separator. Therefore, it is necessary to know all separators of the original graph. An algorithm, which constructs and analyses only all minimal separators, is proposed. This algorithm gives an upper bound for the vertex integrity of the graph. In the first stage, the algorithm computes the set $M$ of all minimal separators of the graph $G$ using a necessary and sufficient condition. The complexity of this stage polynomially depends on the number of vertices of the graph, namely $\mathrm O(n^3)$. In the second stage, each separator in $M$ is substituted into the objective function to find the vertex integrity. The computational complexity of this stage linearly depends on the cardinality of $M$. The experimental results show that the calculated estimates are good and often achievable.
Keywords: graph algorithms, graph vertex integrity, minimum separators. 
@article{PDMA_2015_8_a54,
     author = {V. V. Bykova and Y. I. Kirillov},
     title = {Calculation of upper bounds for graph vertex integrity based on the minimal separators},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {142--144},
     publisher = {mathdoc},
     number = {8},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2015_8_a54/}
}
TY  - JOUR
AU  - V. V. Bykova
AU  - Y. I. Kirillov
TI  - Calculation of upper bounds for graph vertex integrity based on the minimal separators
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2015
SP  - 142
EP  - 144
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2015_8_a54/
LA  - ru
ID  - PDMA_2015_8_a54
ER  - 
%0 Journal Article
%A V. V. Bykova
%A Y. I. Kirillov
%T Calculation of upper bounds for graph vertex integrity based on the minimal separators
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2015
%P 142-144
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2015_8_a54/
%G ru
%F PDMA_2015_8_a54
V. V. Bykova; Y. I. Kirillov. Calculation of upper bounds for graph vertex integrity based on the minimal separators. Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 142-144. http://geodesic.mathdoc.fr/item/PDMA_2015_8_a54/

[1] Bykova V. V., “O merakh tselostnosti grafa”, Prikladnaya diskretnaya matematika, 2014, no. 4(26), 96–111

[2] Barefoot C. A., Entringer R., Swart H. C., “Vulnerability in graphs – a comparative survey”, J. Combin. Math. Combin. Comput., 1 (1987), 13–22 | MR | Zbl

[3] Clark L. H., Entringer R. C., Fellows M. R., “Computational complexity of integrity”, J. Combin. Math. Combin. Comput., 2 (1987), 179–191 | MR | Zbl

[4] Berry A., Bordat J.-P., Structuring the minimal separators of an undirected graphs, Technical Report 152, LIM, Marseille, 1996