Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω ( n , m ) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω ( n , m ) if, for all node-failure probabilities q ∈ ( 0 , 1 ) , the graph G is the most reliable graph in the class of graphs Ω ( n , m ) . This paper proves that the multipartite graphs K ( b , b + 1 , … , b + 1 , b + 2 ) are uniformly optimal in their classes Ω ( ( k + 2 ) ( b + 1 ) , ( k 2 + 3 k + 2 ) ( b + 1 ) 2 / 2 − 1 ) , where k is the number of partite sets of size ( b + 1 ) , while for i > 2 , the multipartite graphs K ( b , b + 1 , … , b + 1 , b + i ) are not uniformly optimal in their classes Ω ( ( k + 2 ) b + k + i , ( k + 2 ) ( k + 1 ) b 2 / 2 + ( k + 1 ) ( k + i ) b + k ( k + 2 i − 1 ) / 2 ) .