Properties of Node Reliability Polynomials

Abstract

We are living in a connected world and failures can occur anywhere at any time probabilistically. In this thesis, we consider networked systems whose links are perfectly reliable and nodes are subject to failure. The probability of a network subjecting to failure to remain connected is named the node reliability of a graph. The node reliability naturally gives rise to a polynomial in the node operational probability $p$. We call this polynomial node reliability polynomial. The research aims to explore the properties of the node reliability polynomial.

Python tools were developed to compute the exact solutions of node reliability polynomial by enumerating all possible connected sets in graphs. Monte-Carlo simulation software in Python was also developed for approximate solutions of graphs that are too large for enumeration. We took advantage of the developed Python tools to investigate the combinatorics aspect of graphs.

The most important result is that we provide a construction method based on the lexicographic product of graphs such that the node reliability polynomials of two graphs, with the same number of nodes and links, can have an arbitrary number of intersection points. In addition, we have discovered that a fully-joint graph’s connected sets are composed by the addition of the connected sets of all partitions along with the connected sets of the complete multi-partite graph that corresponds to the full interconnection between partitions. Later, we propose a conjecture that complete bipartite graphs that are $\kappa$-optimal in their class are node reliability optimal in their class. Last but not least, by enumeration of all non-isomorphic graphs of the order less than 10, we have discovered the minimum orders of graph pairs that their node reliability polynomials intersect one, two, and three times. The performance of the crude Monte-Carlo simulation in simulating node reliability polynomial is discussed as well.