๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Uniformly optimally reliable graphs

โœ Scribed by Gross, D.; Saccoman, J. T.

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
156 KB
Volume
31
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

A graph with n nodes and e edges, where the nodes are perfectly reliable and the edges fail independently with equal probability r, 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 r. UOR simple graphs have been identified in the classes e ร… n 0 1, e ร… n, e ร… n / 1, and e ร… n / 2 (Boesch et al.,. In this paper, we demonstrate that the UOR simple graphs in these classes are also UOR when the classes are extended to include multigraphs.

๐Ÿ“œ SIMILAR VOLUMES

Uniformly least reliable graphs
Uniformly least reliable graphs
โœ Petingi, L.; Saccoman, J. T.; Schoppmann, L. ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 436 KB

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 nod