A simple proof of the Gross‐Saccoman multigraph conjecture. Issue 3 (1st June 2022)

• Record Type: Journal Article
• Authors: Martínez, Mauro; Romero, Pablo; Viera, Julián
• Is Part Of: Networks. Volume 80:Issue 3(2022)
• Page Start: 333
• Page End: 337
• Publication Date: 2022-06-01
• Subjects: graph theory -- Gross‐Saccoman multigraph conjecture -- multigraph -- network reliability -- self‐similarity property -- uniformly most reliable graph; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22110
• Languages: English
• ISSNs: 0028-3045

Abstract

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 m ≤ n + 2 $$ m\le n+2 $$, where n $$ n $$ and m $$ m $$ are the number of nodes and edges of the multigraphs, respectively. They conjectured that the optimality is also achieved by simple graphs when m = n + 3 $$ 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 $$ m\le 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 multigraph conjecture for larger graph classes.