Premium
On the existence of uniformly optimally reliable networks
Author(s) -
Boesch F. T.,
Li X.,
Suffel C.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210204
Subject(s) - undirected graph , graph , combinatorics , mathematics , enhanced data rates for gsm evolution , random geometric graph , discrete mathematics , reliability (semiconductor) , simple (philosophy) , line graph , computer science , voltage graph , telecommunications , power (physics) , philosophy , physics , epistemology , quantum mechanics
A well‐known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. The measure of reliability is then defined to be the probability that the graph is connected. A well‐defined synthesis problem is to find the graph that minimizes the failure probability given the number of nodes n , the number of edges e , and the edge failure rate ρ. In this work, we consider the possibility of the existence of a fixed graph that is optimal for all possible ρ. It is simple to verify that such graphs exist when e = n − 1, or n . Herein, we show that they also exist when e = n + 1 and n + 2.