The structure of max ?-minm?+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 λ = [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 m, graph (i ≥ λ); then we discuss the case of i = X + 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.