Uniformly least reliable graphs

✍ Scribed by Petingi, L.; Saccoman, J. T.; Schoppmann, L.

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 436 KB
• Volume: 27
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199603)27:2<125::aid-net4>3.0.co;2-m

✦ Synopsis

The all-terminal reliability (ATR) of an undirected graph G , denoted as R(G , q ) , is the probability that, when the edges are assigned independent but equal failure probabilities q, 0 < q < 1 (nodes are perfect), the surviving edges induce a spanning connected subgraph of G . A graph G with n nodes and e edges is said to be uniformly least reliable if and only if R(G , q ) I R(G', q ) among all connected G' with the same number of nodes and edges as G and for all failure probabilities 0 < q < 1. In this paper, we characterize uniformly least reliable graphs fore 2 ( n -1 )(n -2)/2 + 1. We note that, unlike general graphs, for which computing the ATR has been shown to be NP-hard, the ATR of these graphs can be computed in polynomial time, providing an efficient lower bound for the general problem. 0 7996 John Wiley & Sons, Inc.