A Simple Proof of the Gross-Saccoman Multigraph Conjecture

Abstract

An enigmatic conjecture in network synthesis asserts that the the uniformly most reliable multigraphs are simple. Daniel Gross and John Saccoman proved in 1998 that the answer is affirmative whenever m ≤ n + 2, where n and m is the respective number of nodes and edges of the multigraphs. They conjectured that the optimality is also achieved by simple graphs when m = n + 3. A proof for this conjecture recently appeared. In this article we provide a unified short proof for the previous cases where m ≤ n + 3. Our proof strategy holds whenever the most reliable simple graphs satisfy the self similarity property. As a consequence, it could be used to study the general multigraph conjecture for larger graph classes.