Premium
On reliability of graphs with node failures
Author(s) -
Goldschmidt Olivier,
Jaillet Patrick,
Lasota Richard
Publication year - 1994
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.3230240407
Subject(s) - combinatorics , indifference graph , mathematics , discrete mathematics , graph , computer science , cograph , pathwidth , node (physics) , class (philosophy) , reliability (semiconductor) , line graph , artificial intelligence , structural engineering , engineering , power (physics) , physics , quantum mechanics
We consider the reliability of graphs for which nodes fail independently of each other with a constant probability 1 ‐ p . The reliability of a graph is defined to be the probability that the induced subgraph of surviving nodes is connected. A graph is said to be uniformly best when, for all choices of p , it is most reliable in the class of graphs with the same number of nodes and same number of edges. In this paper, we first extend the existing known set of uniformly best graphs. Next, we show that most classes of sparse graphs do not contain a uniformly best graph. Finally, we introduce the important notions of locally best and asymptotically best graphs and illustrate these concepts with a detailed study of graphs having the same number of nodes and edges. © 1994 by John Wiley & Sons, Inc.