The average reliability of a graph

J. I. Brown, D. Cox, R. Ehrenborg

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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 languageEnglish
Pages (from-to)19-33
Number of pages15
JournalDiscrete Applied Mathematics
StatePublished - 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 ).


  • All terminal reliability
  • Average reliability
  • Closure
  • Cycle bundles
  • Optimal graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'The average reliability of a graph'. Together they form a unique fingerprint.

Cite this