Premium
On uniformly optimally reliable graphs for pair‐connected reliability with vertex failures
Author(s) -
Amin A. T.,
Siegrist K. T.,
Slater P. J.
Publication year - 1993
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.3230230306
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , discrete mathematics , connectivity
Let G be a probabilistic (n,m) graph in which each vertex exists independently with fixed probability p , 0 < p < 1. Pair‐connected reliability of G , denoted PC v (G;p) , is the expected number of connected pairs of vertices in G . An (n,m) graph G is uniformly optimally reliable if PC v (G;p) ≧ PC v (H;p) for all p , 0 < p < 1, over all (n,m) graphs H . It is shown that there does not exist a uniformly optimally reliable (n,m) graph whenever n ≦ m < ∼2 n 2 /9. However, such graphs do exist for some other values of m . In particular, it is established that every complete k ‐partite pseudoregular graph on n vertices, 2 ≦ k < n , is uniformly optimally reliable. © 1993 by John Wiley & Sons, Inc.