Grafos uniformemente más confiables y grafos fuertes

Abstract

Sea Cn,m la clase de grafos conexos y simples con n vértices y m aristas. El co-rango de Cn,m y de cada uno de sus grafos es igual a m − n + 1. Sea G en Cn,m. Para cada ρ en [0, 1], se define la confiabilidad de G en ρ como la probabilidad de que el subgrafo obtenido de remover cada arista de G independientemente con probabilidad ρ sea conexo. Decimos que G es uniformemente más confiable si para cada H en Cn,m y cada ρ en [0, 1] se cumple que RG(ρ) ≥ RH(ρ). Decimos que un corte de G es un subconjunto de aristas U de G que cumple que G − U no es conexo. El número de cortes de G con k elementos se denota µk(G). Decimos que G es fuerte si para cada H en Cn,m y cada k en {0, . . . , m} se cumple que µk(G) ≤ µk(H). Es cierto que todo grafo fuerte es uniformemente más confiable. Boesch [J. Graph Theory 10 (1986), 339–352] conjeturó que todo grafo uniforme más confiable es fuerte. Se sabe que en cada una de las clases Cn,m cuyo co-rango es 4 o menor existe al menos un grafo uniformemente más confiable, y además cada grafo uniformemente más confiable es fuerte. Si bien existen infinitas clases Cn,m cuyo co-rango es igual a 5, se demostró recientemente que hay tan solo una cantidad finita de dichas clases que tienen un grafo que es uniformemente más confiable. Un proyecto ambicioso consiste en buscar una clase Cn,m que posea un grafo uniformemente más confiable que no sea fuerte. Dicha clase, en caso de existir, refutaría a la conjetura de Boesch. En este proyecto se realiza un estudio computacional relativo a la existencia o inexistencia de grafos uniformemente más confiables y de grafos fuertes dentro de clases Cn,m de co-rango 5.