Uniformly Least Reliable Graphs in Class $\mathrm{\Omega }(n,e)$ as $e\le n+1$

Abstract

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\in \mathrm{\Omega }(n,e)$ is said to be uniformly least reliable if $R(G,p)\le R(G^{\prime },p)$ for all $G^{\prime }\in \mathrm{\Omega }(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 $\mathrm{\Omega }(n,e)$ for $e\le n+1$ and give their topologies.