No label defined (Q3218162)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3884207
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3884207

      Statements

      0 references
      1983
      0 references
      connected graph
      0 references
      regular graph
      0 references
      probability
      0 references
      cut sets
      0 references
      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.
      0 references

      Identifiers