The structure of max ?-minm?+1 graphs used in the design of reliable networks
Guifang Wang, Lianzhu Zhang · Networks · 1997
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 λ = [2e/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 ml 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