Refutación a la conjetura de Boesch para clases de grafos de corango 7.

Abstract

Este proyecto de grado se enmarca en el estudio de confiabilidad de redes. Sea Cn,m la clase de todos los grafos simples y conexos con n vértices y m aristas. Sea G un grafo perteneciente a la clase Cn,m y ρ ∈ [0, 1]. La confiabilidad del grafo G evaluada en ρ, que se denota RG(ρ), es la probabilidad de que el subgrafo que resulta de eliminar a cada una de las aristas de G con probabilidad ρ y de manera independiente sea conexo. Decimos que un grafo G en Cn,m es uniformemente más confiable si para todo grafo H en Cn,m y todo ρ ∈ [0, 1] se cumple que RG(ρ) ≥ RH(ρ). En 1986, Boesch conjeturó que en cada una de las clases no vacías Cn,m existe al menos un grafo que es uniformemente más confiable. El corango de la clase Cn,m y de cada uno de los grafos de dicha clase vale m − n + 1. A partir de la literatura clásica de confiabilidad uniforme se concluye que en cada una de las clases no vacías Cn,m cuyo corango es 4 o menor existe exactamente un grafo que es uniformemente más confiable. Ath y Sobel conjeturaron que cada una de las clases Cn,m cuyo corango es c ∈ {5, 6, 7, 8} tales que n ≥ 2c − 2 tiene exactamente un grafo que es uniformemente más confiable. Recientemente se ha demostrado que existen infinitas clases Cn,m cuyos corangos son 5 o 6 para las cuales no existe ningún grafo uniformemente más confiable, por lo que las conjeturas de Boesch y Ath y Sobel no son ciertas para corangos 5 ni 6. El objetivo de este proyecto consiste en determinar si es cierta la conjetura de Ath y Sobel para aquellas clases de grafos Cn,m que poseen corango 7. Como resultado, hemos refutado la conjetura de Ath y Sobel para corango 7, construyendo al mismo tiempo una nueva familia de contraejemplos para la conjetura de Boesch. Concretamente, hemos demostrado que para cada entero s tal que s ≥ 9 no existe ningún grafo uniformemente confiable en C18s−6,18s. Nuestros estudios reflejan fuerte evidencia computacional de inexistencia de grafos uniformemente más confiables en otras clases de corango 7.