scientific article; zbMATH DE number 3884207

From MaRDI portal
Publication:3218162





Consider finite simple undirected graphs with N vertices and connectivity m in which each vertex has a probability p of failure (removal with its incident edges). Assume that failures of vertices are independent. \textit{H. Frank} [Proc. 3rd Annual Princeton Conf. Inform. Sci. Syst., 1-6 (1969; Zbl 0293.05143)] has described the problem of finding, if p is sufficiently small, graphs with the minimum probability of disconnection among all graphs with mN/2 edges. The author has previously shown that in many cases it is possible to answer Frank's question by constructing a graph with the minimum number of vertex cut sets. He now considers the problem of minimising the expected number E of vertices disconnected from the largest remaining component of the graph (or isolated if all components are isolated vertices). Some graphs constructed by \textit{S. l. Hakimi} and \textit{A. T. Amin} [Networks 3, 241- 260 (1973; Zbl 0272.05124)] have the smallest value of E for some sufficiently small p. However, their result does not indicate how small p must be. The author gives what may be a more practical solution to the problem of minimising E.




Cited in
(29)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3218162)