Uniformly optimal graphs in some classes of graphs with node failures |
| |
Authors: | Shimin Yu Huajun Meng |
| |
Affiliation: | Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, China |
| |
Abstract: | 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),(k2+3k+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)b2/2+(k+1)(k+i)b+k(k+2i−1)/2). |
| |
Keywords: | Network reliability Node failures Multipartite graph Uniformly optimal graph |
本文献已被 ScienceDirect 等数据库收录! |
|