Split Reliability

Abstract

The split reliability of a graph G is the probability that if every edge is independently operational with probability p, every vertex is always operational, and we specify two vertices s and t, that every vertex can communicate with exactly one of s or t. The split reliability is a polynomial. First, we find explicit formulas for the split reliability for various families of graphs. We show that finding split reliability polynomials is intractable. We prove that split reliability polynomials are always alternating in sign. We also find some lower and upper bounds for the split reliability polynomial. Finally, we prove that the value of p that maximizes the probability of split reliability and the maximum probability of split reliability are both dense in the interval [0,1], though this is not the case for all families of graphs.