Uniformly optimally reliable graphs: A survey. Issue 4 (6th December 2021)

• Record Type: Journal Article
• Authors: Romero, Pablo
• Is Part Of: Networks. Volume 80:Issue 4(2022)
• Page Start: 466
• Page End: 481
• Publication Date: 2021-12-06
• Subjects: all‐terminal reliability -- failure type -- graph theory -- two‐terminal reliability -- uniformly least reliable graph -- uniformly most reliable graph; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22085
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: Which is the most reliable graph with n nodes and m edges? This celebrated problem has several aspects, according to the notion of optimality (in a local or uniform sense), failure type (either nodes or edges), or reliability model (all‐terminal connectedness, two‐terminal or multiterminal setting). This article presents a chronological survey of the multiple proposals to address the problem, together with recent trends and enigmatic conjectures posed decades ago that promote further research.