Búsqueda de grafos cúbicos de máxima confiabilidad

Abstract

Un modelo muy popular para el estudio de confiabilidad en redes consiste en modelar la red como un grafo no dirigido, en el que los nodos no fallan y las arista sí lo hacen pero en forma independiente y con la misma probabilidad. La magnitud de interés en este caso es la probabilidad de que el grafo se mantenga conexo frente a dichas fallas, lo que se conoce como confiabilidad all-terminal del grafo. Se ha probado que para ciertas familias de (p,q)-grafos existen grafos que maximizan esta medida de confiabilidad para toda probabilidad de falla de las aristas, los que son conocidos como grafos uniformemente confiables. En este trabajo investigamos la existencia de grafos uniformemente confiables para la familia de (12,18)-grafos y probamos matemáticamente la existencia de un único grafo cúbico uniformemente confiable para la misma, el denominado grafo Yutsis 18j-symbol label F.