On Connectedness and Graph Polynomials

Abstract

Given a graph G whose nodes are perfectly reliable and whose edges fail independently with probability q in [0,1], the all-terminal reliability of G is the probability that all vertices of G can communicate with one another. The all-terminal reliability is a polynomial in q whose roots (all-terminal reliability roots) were conjectured to have modulus at most 1 by Brown and Colbourn. This conjecture was proven false by Sokal and Royle, but only by a slim margin. We present an upper bound on the modulus of any all-terminal reliability root in terms of the number of vertices of the graph. We find all-terminal reliability roots of greater modulus than any previously known, and we study simple graphs with all-terminal reliability roots of modulus greater than 1.

Given a graph G whose edges are perfectly reliable and whose nodes each operate independently with probability p in [0,1], the node reliability of G is the probability that at least one node is operational and that the operational nodes can all communicate in the subgraph that they induce. We explore analytic properties of the node reliability on the interval [0,1] including monotonicity, concavity, and fixed points. Our results demonstrate a stark contrast between this model of network robustness and models that arise from coherent set systems (including all-terminal reliability).

A connected set of a graph G is a nonempty subset of vertices of G that induces a connected subgraph. The conneted set polynomial of G is the generating polynomial of the collection of connected sets of G. The computational complexity, and the nature and location of the roots of the connected set polynomial are investigated. Our results have direct implications for node reliability. Further, we consider the connected set polynomials of trees – the total number of subtrees of a tree has recently garnered much interest and the connected set polynomial extends this notion.