文献类型：期刊文献

英文题名：Uniformly Least Reliable Graphs in Class Ω(n, e) as e ≤ n+1

作者：Meng, Huajun[1];Shao, Fang-Ming[1];Lu, Xiwen[1]

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

年份：2010

卷号：97

起止页码：217

外文期刊名：ARS COMBINATORIA

收录：;WOS:【SCI-EXPANDED(收录号:WOS:000282532100021)】；

语种：英文

外文关键词：all-terminal reliability; Boesch's conjecture; uniformly least reliable graphs

摘要：We consider the undirected simple connected graph for which edges fail independently of each other with equal probability 1 p and nodes are perfect. The all-terminal reliability of a graph G is the probability that the spanning subgraph of surviving edges is connected, denoted as R(G,p). Graph G is an element of Omega(n, e) is said to be uniformly least reliable if R(G,p) <= R(G',p) for all G' E 0(n, e), and for all edge failure probabilities 0 < 1 p < 1. In this paper, we prove the existence of uniformly least reliable graphs in the class Omega(n, e) for e < n 1 and give their topologies.