An Overview of Network Reliability

Abstract: We assume that in a finite undirected graph all vertices are always working, but edges are independently operational with probability p. The (all-terminal) reliability of a graph is the probability that all vertices can communicate. This notion of reliability provides a measure of robustness to the network, and the most interesting questions straddle the line between pure an applied mathematics, between graph theory and computer science, and between combinatorics and other branches of mathematics. In this talk I'll give an overview of the most pertinent issues and results.