A simple proof of the Gross‐Saccoman multigraph conjecture
Mauro Martínez, Pablo Romero, Julián Viera · Networks · 2022
Abstract An enigmatic conjecture in network synthesis asserts that uniformly most reliable multigraphs are simple. Daniel Gross and John Saccoman proved in 1998 that the answer is affirmative whenever , where and are the number of nodes and edges of the multigraphs, respectively. They conjectured that the optimality is also achieved by simple graphs when . A proof for this conjecture recently appeared. In this article we provide a unified short proof for the previous cases where . 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 multigraph conjecture for larger graph classes.