Premium
Rational roots of all‐terminal reliability
Author(s) -
Brown Jason I.,
DeGagné Corey D. C.
Publication year - 2020
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21938
Subject(s) - mathematics , combinatorics , terminal (telecommunication) , spanning tree , rational number , moduli , class (philosophy) , reliability (semiconductor) , discrete mathematics , graph , order (exchange) , computer science , power (physics) , physics , quantum mechanics , telecommunications , finance , artificial intelligence , economics
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.