Título : | A Simple Proof of the Gross-Saccoman Multigraph Conjecture |
Autor(es) : | Martínez, Mauro Romero, Pablo Viera, Julián |
Fecha de publicación : | 1-jun-2022 |
Tipo de publicación: | Artículo |
Versión: | Enviado |
Publicado por: | Wiley |
Publicado en: | Networks |
Areas del conocimiento : | Ciencias Naturales y Exactas Matemáticas Matemática Aplicada |
Otros descriptores : | Network Reliability Gross-Saccoman multigraph conjecture Graph Theory Uniformly Most Reliable Graph Self Similarity Property Multigraph |
Resumen : | 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. |
URI / Handle: | https://hdl.handle.net/20.500.12381/701 |
DOI: | 10.1002/net.22110 |
Institución responsable del proyecto: | Universidad de la República Universidad de Buenos Aires |
Financiadores: | Agencia Nacional de Investigación e Innovación |
Identificador ANII: | FCE_1_2019_1_156693 |
Nivel de Acceso: | Acceso abierto |
Licencia CC: | Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional. (CC BY-NC-ND) |
Aparece en las colecciones: | Publicaciones de ANII |
Archivos en este ítem:
archivo | Descripción | Tamaño | Formato | ||
---|---|---|---|---|---|
9 (1).pdf | Descargar | GS - Simple Proof | 142.87 kB | Adobe PDF |
Las obras en REDI están protegidas por licencias Creative Commons.
Por más información sobre los términos de esta publicación, visita:
Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional. (CC BY-NC-ND)