| Article ID: | iaor1992944 |
| Country: | Switzerland |
| Volume: | 33 |
| Start Page Number: | 107 |
| End Page Number: | 112 |
| Publication Date: | Dec 1991 |
| Journal: | Annals of Operations Research |
| Authors: | Smith D.H. |
| Keywords: | networks |
The paper considers the probability of disconnection of a graph as a measure of network reliability. It compares the vertex and edge failure cases, and then concentrates on the vertex failure case. Optimal graphs are graphs which minimise the probability of disconnection for a given number of vertices and edges when the probability of vertex failure is small. The paper describes the known results on the construction of optimal regular graphs and presents some new results on the construction of optimal nonregular graphs.