文献类型：期刊文献

英文题名：Uniformly optimal graphs in some classes of graphs with node failures

作者：Yu, Shimin[1];Shao, Fang-Ming[1];Meng, Huajun[1]

机构：[1]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2010

卷号：310

期号：1

起止页码：159

外文期刊名：DISCRETE MATHEMATICS

收录：;EI(收录号：20094612449518);WOS:【SCI-EXPANDED(收录号:WOS:000272437800018)】；

语种：英文

外文关键词：Network reliability; Node failures; Multipartite graph; Uniformly optimal graph

摘要：The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Omega(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 Omega(n, m) if, for all node-failure probabilities q is an element of (0, 1), the graph G is the most reliable graph in the class of graphs Omega(n, m). This paper proves that the multipartite graphs K(b, b + 1,..., b + 1, b + 2) are uniformly optimal in theirclasses Omega((k + 2)(b + 1), (k(2) + 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 theirclasses Omega((k + 2)b + k + i, (k + 2)(k + 1)b(2)/2 + (k + 1)(k + i)b + k(k + 2i - 1)/2). (C) 2009 Elsevier B.V. All rights reserved.