The average reliability of a graph

In this paper we introduce the average reliability   of a graph GG, avgRel(G), which is average value of the all terminal reliability of a graph GG on [0,1][0,1]. We show that while the determination of the average reliability of a graph is apparently intractable, it can be efficiently bounded. We show that the closure of the average reliabilities is the interval [0,1][0,1]. Finally, while in general there do not exist uniformly optimal graphs with respect to reliability, we apply average reliability to propose “good” graphs for network reliability, and provide evidence that a specific family of cyclic graphs are indeed good.