Reliability Polynomials of Chorded Cycle Graphs
Dana Loughrey · Seton Hall University eRepository (Seton Hall University) · 2015
We denote by C c1,c2 c+x the graphs comprised of a cycle on c nodes having a single chord, with c1 and c2 cycle nodes on either side of the chord. When a graph is used to model a network, the All-Terminal Reliability (Rel) is the probability of network communication among all stations when the stations are perfectly reliable and the links fail with equal but independent probability. Thus, Rel(G , p) = ∑|E(G)| i=0 Ni p i (1 − p)|E(G)|−i , where E (G ) is the total number of edges, p is the probability of edge operation, and Ni is the number of spanning connected subgraphs of size i . We present formulas for the Rel for all chorded cycle graphs having finite c , and prove that the uniformly most reliable such graph is the one in which c1 = c2 when c is even, and in which c1 and c2 differ by one when c is odd. Dana Loughrey (Seton Hall University) Reliability Polynomials of Chorded Cycle Graphs May 1, 2015 2 / 2