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
1983
0 references
connected graph
0 references
regular graph
0 references
probability
0 references
cut sets
0 references
0.8551159501075745
0 references
0.8535504341125488
0 references
0.8470326066017151
0 references
0.8464522361755371
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