## On Connectedness and Graph Polynomials

##### Author

Mol, Lucas

##### Metadata

Show full item record##### 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.