Consider a connected graph G , and assume that every edge fails independently with probability q . The (all-terminal) reliability polynomial is the probability in 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 ] where β ≈ − 0 . 5707202942 .

Abstract We introduce two new methods for approximating the all‐terminal reliability of undirected graphs. First, we introduce an edge removal process: remove edges at random, one at a time, until the graph becomes disconnected. We show that the expected number of edges thus removed is equal to , where is the number of edges in the graph, and is the average of the all‐terminal reliability polynomial. Based on this process, we propose a Monte‐Carlo algorithm to quickly estimate the graph reliability (whose exact computation is NP‐hard). Moreover, we show that the distribution of the edge removal process can be used to quickly approximate the reliability polynomial. We then propose increasingly accurate asymptotics for graph reliability based solely on degree distributions of the graph. These asymptotics are tested against several real‐world networks and are shown to be accurate for sufficiently dense graphs. While the approach starts to fail for “subway‐like” networks that contain many paths of vertices of degree two, different asymptotics are derived for such networks.

Abstract A common model of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability . One can ask for the probability that all vertices can communicate (all‐terminal reliability) or that two specific vertices (or terminals) can communicate with each other (two‐terminal reliability). A relatively new measure is split reliability, where for two fixed vertices and , we consider the probability that every vertex communicates with one of or , but not both. In this article, we explore the existence for fixed numbers and of an optimal connected ‐graph for split reliability, that is, a connected graph with vertices and edges for which for any other such graph , the split reliability of is at least as large as that of , for all values of . Unlike the similar problems for all‐terminal and two‐terminal reliability, where only partial results are known, we completely solve the issue for split reliability, where we show that there is an optimal ‐graph for split reliability if and only if , , or .

Abstract A variety of probabilistic notions of network reliability of graphs and digraphs have been proposed and studied since the early 1950s. Although grounded in the engineering and logistics of network design and analysis, the research also spans pure and applied mathematics, with connections to areas as diverse as combinatorics and graph theory, combinatorial enumeration, optimization, probability theory, real and complex analysis, algebraic topology, commutative algebra, the design and analysis of algorithms, and computational complexity. In this paper we describe the landscape of various notions of network reliability, the roads well traveled, and some that appear likely to lead to meaningful and important journeys.

Abstract Assume that the vertices of a graph G are always operational, but the edges of G are operational independently with probability p ∈ [0, 1]. For fixed vertices s and t, the two‐terminal reliability of G is the probability that the operational subgraph contains an (s, t)‐path, while the all‐terminal reliability of G is the probability that the operational subgraph contains a spanning tree. Both reliabilities are polynomials in p, and have very similar behavior in many respects. However, unlike all‐terminal reliability polynomials, little is known about the roots of two‐terminal reliability polynomials. In a variety of ways, we shall show that the nature and location of the roots of two‐terminal reliability polynomials have significantly different properties than those held by roots of the all‐terminal reliability polynomials.

Abstract Given a connected graph G whose vertices are perfectly reliable and whose edges each fail independently with probability q ∈ [0, 1], the (all‐terminal) reliability of G is the probability that the resulting subgraph of operational edges contains a spanning tree (this probability is always a polynomial in q). The location of the roots of reliability polynomials has been well studied, with particular interest in finding those with the largest moduli. In this paper, we will discuss a related problem—among all reliability polynomials of graphs on n vertices, what can we say about the rational roots? We prove that (for n ≥ 2), the rational roots are −1, − 1/2, − 1/3,…, − 1/(n − 1), 1. Moreover, we show that for n ≥ 3, the root of minimum modulus among all graphs of order n is rational, and determine all roots of smallest moduli and the corresponding graphs. Finally, we provide the first nontrivial mathematical property that distinguishes, via reliability, the class of simple graphs (i.e., those without loops and multiple edges) from that of graphs in general.

Suppose we have a graph G (finite and undirected) where the vertices of G are always operational, but the edges of G operate independently with probability . The all-terminal reliability of a graph G is the probability that every pair of vertices in G is connected by a path: that is, some spanning tree is operational. We prove that the points of inflections of all-terminal reliability polynomials are dense in [0,1]. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 266–269 2016

Given a graph G whose edges are perfectly reliable and whose nodes each operate independently with probability 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; it is the analogous node measure of robustness to the well studied all‐terminal reliability, where the nodes are perfectly reliable but the edges fail randomly. In sharp contrast to what is known about the roots of the all‐terminal reliability polynomial, we show that the node reliability polynomial of any connected graph on at least three nodes has a nonreal polynomial root, the collection of real roots of all node reliability polynomials is unbounded, and the collection of complex roots of all node reliability polynomials is dense in the entire complex plane. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(3), 238–246 2016

Abstract Suppose that every edge of a graph G (finite and undirected) is independently operational with probability . The all terminal reliability of G is the probability that all vertices can communicate. It was conjectured that among all graphs with n vertices and m edges there always exists a most optimal graph, that is, one whose all terminal reliability is at least as large as any other such graph, no matter what the value of p. For each , a single value of m was found for which the restriction of the conjecture to simple graphs failed, but it remained open as to whether most optimal graphs exist when multiple edges are allowed. We show that in fact for a given , there are several values of m for which a most optimal simple graph does not exist. Moreover, we prove that including multiple edges still does not introduce a most optimal graph, disproving for the first time the conjecture for general graphs. In contrast, it will be shown that for a given n and m, there always exists a least optimal graph. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 146–153 2014

Abstract The strongly connected reliability scRel(D, p) of a digraph D is the probability that the spanning subgraph of D consisting of the operational arcs is strongly connected, given that the vertices always operate, but each arc independently operates with probability p ∈ [0, 1]. We provide here some results on the location of the roots of strongly connected reliability polynomials that contrast sharply with what is known for all terminal reliability. We show that not only there can be negative real roots, but also roots of arbitrarily large modulus. In fact, the closure of the roots of strongly connected reliability polynomials contains all of the complex plane except, possibly, some subset of the unit disk centered at z = 1. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Boesch et al. conjectured that for any n and m there exists a uniformly optimal (n,m)–graph Gn,m for all terminal reliability, that is, the all‐terminal reliability of Gn,m is at least as large as the all‐terminal reliability of any other graph G with n vertices and m edges, no matter what the probability of an edge being operational is. Although there are counterexamples known when one restricts attention to simple graphs, the conjecture remains open when one allows parallel edges. We consider the analogous problem for strongly connected reliability, that is, the probability that a digraph contains a spanning strongly connected subdigraph, given that each vertex is operational, but arcs are independently operational with probability p. We show that there do indeed exist uniformly optimal digraphs for strongly connected (n,m)–digraphs. We also show that if one restricts attention to simple digraphs (without parallel arcs) then such uniformly optimal digraphs need not exist. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 145–151 2007

Abstract Given a digraph D, consider the model where each vertex is always operational, but the edges are independently operational with probability p. The strongly connected reliability of D, scRel(D,p), is the probability that the spanning subgraph of D consisting of the operational edges is strongly connected. One can view strongly connected reliability as the probability that any vertex can send information to any other vertex, given that edges fail independently. There are very few classes for which there is an efficient algorithm for calculating the strongly connected reliability. This article presents the fist polynomial time algorithm for computing the strongly connected reliability of complete digraphs, that is, digraphs in which every vertex is joined to every other vertex by exactly one edge (one in each direction). © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 165–168 2005

For any field ${\bf F}$, the set of all functions $f : V(G) \rightarrow {\bf F}$ whose sum on each maximal independent set is constant forms a vector space over ${\bf F}$. In this paper, we show that the dimension can vary depending on the characteristic of the field. We also investigate the dimensions of these vector spaces and show that while some families, such as chordal graphs, have unbounded dimension, other families, such as nonempty circulant graphs of prime order, have bounded dimension.

For any simplicial complex $\Delta $ and field K, one can associate a graded K-algebra $K[\Delta ]$ (the Stanley–Reisner ring). For certain $\Delta $ and K, the Stanley–Reisner rings have a homogeneous system of parameters, $\Theta $, such that $K[\Delta ]/\langle \Theta \rangle $ is finite-dimensional, and coefficients of its Hilbert series are the h-vector of $\Delta $. The previous constructions of $\Theta $ were noncombinatorial. In the special case of cographic matroids, we give (for any field K) a combinatorial description of a homogeneous system of parameters in terms of the graph structure, as well as an explicit basis for the resulting quotient algebra. The results have applications to a central problem of reliability, namely the association of a multicomplex to a connected graph, such that the reliability is a simple function of the rank numbers.

Let $\beta (G)$ denote the independence number of a graph G. We introduce $A(G) = \lim_{k \to \infty } \beta (G^k )/| V(G) |^k $, where the categorical graph product is used. This limit, surprisingly, lies in the range $( 0,1/2 ] \cup \{ 1 \}$. We can show that this limit can take any such rational number, but is there any G for which $A(G)$ is irrational? A useful technique for bounding $A(G)$ is to consider special spanning subgraphs. These bounds allow us to efficiently compute $A(G)$ for many G. We give a condition which if true for G shows that $A(G) > \beta (G)/| V(G) |$. This brings up the question; for which G does $A(G) = \beta (G)/| V(G) |$? This happens if G is a Cayley graph of an Abelian group or if G is a connected graph that has an automorphism which has a single orbit.

Abstract Three transformations on networks that reduce the all‐terminal network reliability (probability of connectedness) of a network are shown not to increase any coefficient in one form of the reliability polynomial of the network. These transformations yield efficiently computable lower bounds on each coefficient of the reliability polynomial. A further transformation due to Lomonosov is shown not to decrease any coefficient in the reliability polynomial, leading to an efficiently computable upper bound on each coefficient. The resulting bounds on coefficients can, in turn, be used to obtain a substantial improvement on the Ball—Provan strategy for computing lower and upper bounds on the all‐terminal reliability. © 1993 John Wiley & Sons, Inc.

The reliability of a graph G is the probability that G is connected, given that edges are independently operational with probability p. This is known to be a polynomial in p, and the location of the roots of these functions is discussed. In particular, it is conjectured that the roots of the reliability polynomial of any connected graph lie in the disc $| z - 1 | \leq 1$, and evidence for this conjecture is provided. It is shown that all real roots lie in $\{ 0 \} \cup ( 1,2 ]$ and that every graph has a subdivision for which the roots of the reliability polynomial lie in the conjectured disc.

In order to relate the chromatic and all-terminal reliability polynomials, a simple two-variable polynomial is introduced. The latter polynomial is defined on a set system; as a result, many similarities between the chromatic and all-terminal reliability polynomials can be derived. In fact, within this general framework it is often possible to generalize from one of these two graph polynomials in order to get new results for the other.