Various polynomials appear in graph theory: chromatic polynomials, flow polynomials, all-terminal reliability polynomials. All these polynomials are special instances of the Tutte polynomial, and the location of their complex zeros has been actively studied (Biggs, Brown & Colbourn, Chang & Shrock, Royle, Sokal, Welsh, to name but a few). General results have been established for the zeros of recursively defined families of polynomials (Beraha, Kahane, and Weiss): the zeros aggregate asymptotically to sets of algebraic curves and sometimes to isolated points.
In this contribution, we address the two-terminal (or end-to-end) reliability polynomial Rel2, which corresponds to the connectivity of two sites of a graph. Admittedly, this is no graph invariant. However, instead of using the variable $p$ for the (uniform) probability for correct operation of the edges of the graph, we may now consider two variables $p$ and $\rho$ for the edge and site reliabilities, respectively. For a given graph and a pair of sites, we can study the location of the complex zeros of Rel2($p$,$\rho$) as a function of $\rho$.
We present results on a few recursive families of graphs for which the two-terminal reliability polynomial may be computed exactly as a function of $p$,$\rho$ and $n$ (the size of the graph); the associated generating functions have also been derived. The asymptotic (for $n$ going to infinity) location of zeros has been investigated and exhibits:
- the usual sets of algebraic curves,
- appearing (or disappearing) sets of isolated zeros in some cases,
- an expansion of the general structure as $\rho$ goes to 0, which can be described by a power law.
The set of zeros also undergoes several structural transitions at specific, critical values $\rho_c$ --- which are algebraic --- as $\rho$ decreases from 1 to 0.
More surprisingly, by slightly changing the building blocks of the recursive graphs, we may also numerically observe:
- particular values of $\rho$ for which the sets of zeros look much smoother,
- existence (or not!) of several prevailing sets of isolated zeros with different symmetries (of orders 3 and 13, for instance),
- different ``exploding'' families of algebraic curves with different symmetries and expansion rates, too.
Asymptotic, analytical expressions for the above phenomena can actually be deduced from the generating function.
view more