Portal de Periódicos da CAPES

On the nonexistence of uniformly optimal graphs for pair‐connected reliability

1991; Wiley; Volume: 21; Issue: 3 Linguagem: Inglês

10.1002/net.3230210307

1097-0037

Ashok T. Amin, Kyle Siegrist, Peter J. Slater,

Graph theory and applications

Abstract We consider probabilistic graphs G = (V, E) in which each edge xy ∈ E fails independently with probability q . The reliability measure studied is pair‐connectivity, the expected number of pairs of connected vertices. We examine how the coefficients of the pair‐connected reliability polynomial are determined by the subgraph structure of G , and we use these results to show that in most cases there does not exist a uniformly optimal n ‐vertex, m ‐edge graph.