WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 12, 2013
On Component Order Edge Reliability and the Existence of Uniformly Most Reliable Unicycles
Authors: , , , , ,
Abstract: Let G be a graph with n nodes and e edges, where the nodes are perfectly reliable and the edges fail independently with equal probability ρ A failure state exists if the surviving edges induce a graph having all components of order less than a preassigned threshold value k. The unreliability of G,Uk(G; ρ), is the probability of a failure state and a graph G is k-uniformly most reliable (k-UMR) over a class of graphs if and only if Uk(G; ρ) ≤ Uk(H; ρ) for all 0 < ρ < 1 and all H in the same class as G. If Uk(G; ρ) ≥ Uk(H; ρ) for all 0 < ρ < 1 and all H in the same class as G then G is k- uniformly least reliable (k- ULR). In this paper we show that $$K1, _{n−1} $$ is the unique tree that is k-UMR over all trees with 2 ≤ k ≤ n. We also show that the unicycle $$U_{s}^{x} $$, i.e. $$K1, _{n−1} $$ with an added edge, is uniquely 3-UMR over all graphs having n ≥ 5 nodes and e = n edges. We extend this study for $$4 ≤ k ≤ \frac{n}{2} $$ and prove that $$U_{s}^{x} $$ s the unique k-UMR unicycle In the last two sections we give the necessary conditions for a graph to be k-UMR and show that there exists a range of values of k for which a k-UMR unicycle does not exist.