The structure of max λ‐min m λ+1 graphs used in the design of reliable networks

It was proved that the design problem of the reliable networks for “small” edge failure probability is equivalent to finding a max λ‐min m λ graph for given numbers of nodes n and edges e with λ = [2 e / n ] by Bauer et al. Furthermore, at least a max λ‐min m λ graph was given for each pair of n and e (≥ n ) in another paper by Bauer et al. In the present paper, we first generalize the notion of a max λ‐min m λ graph to a max λ‐min m l graph ( l ≥ λ); then we discuss the case of l = λ + 1 and show that any max λ‐min m λ+1 graph is max λ‐min m λ and give at least a max λ‐min m λ+1 graph for each pair of positive integers n and e . © 1997 John Wiley & Sons, Inc. Networks 30: 231–242, 1997