Abstract
In this paper we introduce the average reliability of a graph G, avgRel(G), which is average value of the all terminal reliability of a graph G on [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]. 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.
Original language | English |
---|---|
Pages (from-to) | 19-33 |
Number of pages | 15 |
Journal | Discrete Applied Mathematics |
Volume | 177 |
DOIs | |
State | Published - Nov 20 2014 |
Bibliographical note
Funding Information:This research was partially supported by grant RGPIN 170450-2013 from Natural Sciences and Engineering Research Council of Canada and the National Science Foundation ( DMS 0902063 ).
Keywords
- All terminal reliability
- Average reliability
- Closure
- Cycle bundles
- Optimal graph
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics