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)Ω(n,m) of all graphs with nn nodes and mm edges in which nodes fail independently and edges never fail. The graph GG is called uniformly optimal in Ω(n,m)Ω(n,m) if, for all node-failure probabilities q∈(0,1)q∈(0,1), the graph GG is the most reliable graph in the class of graphs Ω(n,m)Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2)K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k2+3k+2)(b+1)2/2−1)Ω((k+2)(b+1),(k2+3k+2)(b+1)2/2−1), where kk is the number of partite sets of size (b+1)(b+1), while for i>2i>2, the multipartite graphs K(b,b+1,…,b+1,b+i)K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b2/2+(k+1)(k+i)b+k(k+2i−1)/2)Ω((k+2)b+k+i,(k+2)(k+1)b2/2+(k+1)(k+i)b+k(k+2i−1)/2).