Abstract 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 PCv(G;p), is the expected number of connected pairs of vertices in G. An (n,m) graph G is uniformly optimally reliable if PCv(G;p) ≧ PCv(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 < ∼2n2/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.

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.

Grey-level transformations on digitized images are variously used to minimize storage requirements or to enhance low-level contrast information. A graph-theoretic approach is proposed to implement these transformations. In particular, an efficient algorithm is given for transformation leading to almost uniform grey-level distribution.

Preparata, Metze, and Chien [1] gave necessary conditions for identification of all faulty units in a system S capable of automatic fault diagnosis. We show that these conditions are sufficient if in S no two units test each other. Necessary and sufficient conditions are also obtained for the general case when no such restriction is placed on S.

Abstract This paper is concerned with construction of graphs, with n vertices and m edges, whose connectivity r = [2m/n] ≧ 3, and have no more than n minimum vertex cut‐sets. Frank's results imply that this is an important step in the design of a class of reliable networks.