Uniformly optimally reliable graphs

Journal Article


A graph with n nodes and e edges, where the nodes are perfectly reliable and the edges fail independently with equal probability ρ, is said to be uniformly optimally reliable (UOR) if it has the greatest reliability among all graphs with the same number of nodes and edges for all values of ρ. UOR simple graphs have been identified in the classes e = n − 1, e = n, e = n + 1, and e = n + 2 (Boesch et al., Networks21 (199) 181–194). In this paper, we demonstrate that the UOR simple graphs in these classes are also UOR when the classes are extended to include multigraphs. © 1998 John Wiley & Sons, Inc. Networks 31: 217–225, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.