On the Real Reliability Roots of Graphs

Jason I. Brown, Isaac McMullin · 2026

Read On the Real Reliability Roots of Graphs by Jason I. Brown, Isaac McMullin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09059.txt.

Introduction

Jason Brown and Isaac McMullin prove that nearly all graphs carry a nonreal reliability root. In a connected graph where each edge fails alone with chance q, the reliability polynomial gives the chance the live edges stay linked. They also show reliability roots lie dense on an interval from about negative 0.5707202942 to zero.

Catalog record

CREATORJason I. Brown, Isaac McMullin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21653
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.09059

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Real Reliability Roots of Graphs Jason I. Brown, Isaac McMullin Abstract Consider a connected graph G G , and assume that every edge fails independently with probability q q . The (all-terminal) reliability polynomial is the probability in q q that the spanning connected subgraph of operational edges is connected. In this paper we focus on the real roots of reliability polynomials ( reliability roots ). We prove that almost every graph has a nonreal reliability root, and that the reliability polynomials of graphs have roots dense on the interval [ β , 0 ] [\beta,0] where β ≈ − 0.5707202942 \beta\approx-0.5707202942 . Keywords : graph, reliability, roots, real-rootedness, corank, split reliability Proposed running head : Real Reliability Roots of Graphs 1 Introduction A multigraph G=(V,E) consists of a finite vertex set V and a finite edge multiset E consisting of unordered pairs of elements of V (the order and size of G are, respectively, |V| and |E| ). A simple graph, or simply a graph , is one where E is a set (that is, there are no multiple edges). For standard graph theory terminology we refer the reader to [ 16 ] . There are many ways to model a network’s robustness against random failure. One of the most common ways is as follows. Suppose that every vertex of a multigraph G (we assume from here on in that all multigraphs and graphs are always connected) is always “operational” but each edge independently fails with probability q\in[0,1] (so each edge is independently operational with probability p=1-q ). The (all-terminal) reliability \mbox{Rel}(G;q) of graph G is the probability that for any two vertices u and v , there is a path of operational edges joining them, that is, that the spanning subgraph of G consisting of the operational edges is connected. The history of reliability, in both theoretical and applied settings, is old and well established (see, for example, [ 10 ] ). For a graph G , its reliability can be expressed as \displaystyle\mbox{Rel}(G;q) \displaystyle= \displaystyle\sum_{E^{\prime}}(1-q)^{|E^{\prime}|}q^{|E|-|E^{\prime}|} where the sum is taken over all E^{\prime} such that the spanning subgraph of G with edge set E^{\prime} is connected. We see immediately that reliability functions are always polynomials in q (and p ), and hence we can refer to reliability polynomials . For many graph polynomials, what has attracted attention is the shape of the coefficients of the polynomials, with many results and conjectures centering on unimodality – the observation that the coefficient sequence is nondecreasing then nonincreasing. Indeed the coefficients of various expansions of the reliability polynomial had all been conjectured to be unimodal (see [ 10 ] ), and only recently has this been confirmed for some sequences [ 1 , 14 ] , with proofs using deep techniques from algebraic geometry. A famous – and beautiful! – theorem due to Newton (see, for example [ 11 ] ) proves that if a polynomial with positive coefficients has all real roots (i.e. is real-rooted ) then the coefficient sequence is unimodal. This observation has led many to explore the real (and complex) roots of various graph polynomials, including chromatic polynomials , matching polynomials , independence polynomials , domination polynomials , and indeed reliability polynomials (see, for example, [ 12 , 13 , 9 , 2 , 8 , 4 ] ). And indeed, while some graph polynomials, such as matching polynomials, always have all real roots, most graph polynomials have real and nonreal roots, and characterizing when the roots are always real (i.e. the polynomial is real-rooted) has been of considerable interest. Some families of graphs, such as trees and cycles (the graphs of respectively corank d=m-n+1 of 0 and 1 ) have all real reliability roots. For corank d=2 , there are graphs that have nonreal reliability roots. The \Theta -graph, consisting of two vertices x and y joined by internally disjoint paths of lengths l_{1},l_{2},l_{3} , with 1\leq l_{1}\leq l_{2}\leq l_{3} , has all real reliability roots if and only if l_{1}\leq l_{2}+l_{3}-2\sqrt{l_{2}l_{3}}=(\sqrt{l_{3}}-\sqrt{l_{2}})^{2} . Even the multigraph B_{k} consisting of a bundle of k edges between two vertices has nonreal reliability roots – the reliability polynomial of B_{k} is 1-q^{k} , which has all real roots if and only if k=1 or 2 . While it is not the case that every reliability root is real, in [ 4 ] it was shown that for any multigraph G there exists a subdivision G^{\prime} (and hence infinitely many subdivisions) such that the reliability roots of G^{\prime} are all real. Despite this, the question of how common real-rootedness is for reliability polynomials has never been explored. The closure of the real roots of reliability polynomials of multigraphs is precisely [-1,0]\cup\{1\} [ 4 ] . However, the proof in [ 4 ] uses multigraphs in an essential way, and so the corresponding problem for graphs seems much more subtle and difficult. This paper will address two main questions: 1. How common is real-rootedness for reliability polynomials of graphs? 2. What is the closure of the real roots of reliability polynomials of graphs? 2 Almost All Graphs Have a Nonreal Reliability Root In the context of graphs, we can consider the well-known model \mathcal{G}(n,\rho) of Erdős-Rényi random graphs (see, for example, [ 3 ] ) and ask how common real-rootedness of reliability polynomials is. One might suspect from the result on graph subdivisions that real-rootedness is fairly common, but we shall see that this is far from the truth. To do so, we need to write a couple of different expansions of the reliability polynomial (see, for example, [ 10 ] for this and the following discussion of the forms). If G is a graph of order n and size m (i.e. G is an (n,m) -graph) then setting d=m-n+1 , the corank of G , the F -form of the reliability polynomial is given by \displaystyle\mbox{Rel}(G;q) \displaystyle= \displaystyle\sum_{i=0}^{d}F_{i}q^{i}(1-q)^{m-i}. Here F_{i} is the number of subsets of i edges from G whose removal leaves the graph connected. The set of all such subsets of E(G) forms a simplicial complex , that is, a collection of sets closed under subsets, called the cographic matroid of G . Any matroid is partitionable into intervals (see [ 10 ] for a definition). If H_{i} is the number of intervals in our partition of the cographic matroid whose smallest set is of size i , the H -form of the reliability polynomial is given by \displaystyle\mbox{Rel}(G;q) \displaystyle= \displaystyle(1-q)^{n-1}\sum_{i=0}^{d}H_{i}q^{i}. The connection between the F - and H -forms is \displaystyle F_{k} \displaystyle= \displaystyle\sum_{r=0}^{k}H_{r}{d-r\choose k-r} (1) for k=0,1,\ldots,d . We call the vectors <F_{0},F_{1},...,F_{m-n+1}> and <H_{0},H_{1},...,H_{m-n+1}> the F -vector and the H -vector respectively for the graph G . It is well known that all of the F_{i} ’s and H_{i} ’s are positive integers [ 10 ] and in fact both vectors are unimodal [ 1 , 14 ] . Some additional notation is needed. A set of edges is a cutset if the removal of those edges results in the graph becoming disconnected. Let c_{i} be the number of edge cutsets of G of size i . We begin with the following result. Proposition 2.1 . Let G be a connected multigraph

Read the complete text