Infinitely Many Counterexamples to Conjectures by Boesch and Ath‐Sobel

ABSTRACT Let be the set of connected simple graphs on vertices and edges. Define the corank of as . Let be in and . The reliability is the probability of being connected after each of its edges is removed independently with probability . The graph is a uniformly most reliable graph (UMRG) if for every in and for all . In 1986, Boesch conjectured that each nonempty class contains at least one UMRG. A few years later, Boesch et al. and Wang proved that each class having corank up to 4 includes one UMRG. However, infinitely many counterexamples to the Boesch conjecture appeared. Ath and Sobel conjectured that the Boesch conjecture holds when the corank is between 5 and 8, provided the number of vertices is at least . Recently, it was proved that there are only finitely many UMRGs having corank 5, in strong contrast with graph classes having corank up to 4. A natural question is the existence of UMRGs having corank 6. Here, it is proved that for each positive integer there is no UMRG on vertices having corank 6. This result provides new families of counterexamples to the Boesch and Ath‐Sobel conjectures proposed respectively in 1986 and 2000.