Uniformly Most-Reliable Graphs and Antiholes

In network design, the all-terminal reliability maximization is of paramount importance. In this classical setting, we assume a simple graph with perfect nodes but independent link failures with identical probability \(\rho \). The goal is to communicate p terminals using q links, in such a way that the connectedness probability of the resulting random graph is maximum. A graph with p nodes and q links that meets the maximum reliability property is called uniformly most-reliable (p, q)-graph (UMRG). The discovery of these graphs is a challenging problem that involves an interplay between extremal graph theory and computational optimization. Recent works confirm the existence of special cubic UMRG, such as Wagner, Petersen and Yutsis graphs. To the best of our knowledge, there is no prior works from the literature that find 4-regular UMRG. In this paper, we revisit the breakthroughs in the theory of UMRG. Finally, we mathematically prove that the complement of a cycle with seven nodes, \(\overline{C_7}\), is a 4-regular UMRG. This graph is also identified as an odd antihole using terms from perfect graph theory.