Nonexistence of uniformly most reliable graphs of least corank

Abstract

If G is a simple graph and ρ ∈ [0, 1], the reliability RG(ρ) is the probability of G being connected after each of its edges is removed independently with probability ρ. A simple graph G is a uniformly most reliable graph (UMRG) if RG(ρ) ≥ RH (ρ) for every ρ ∈ [0, 1] and every simple graph H on the same number of vertices and edges as G. Boesch (1986) conjectured that, if n and m are such that there exists a connected simple graph on n vertices and m edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch’s conjecture were given by Kelmans, Myrvold et al., and Brown and Cox. It is known that Boesch’s conjecture holds whenever the corank, defined as c = m − n + 1, is at most 4 (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch’s conjecture holds whenever the corank c is between 5 and 8, provided the number of vertices is at least 2c − 2. In this work, we give an infinite family of counterexamples to Boesch’s conjecture of corank 5. These are the first reported counterexamples that attain the minimum possible corank. As a byproduct, the conjecture by Ath and Sobel is disproved.