Grafos con dos terminales uniformemente más confiables bajo el modelo de falla de vértices : La conjetura de Brown es cierta cuando d=4

Abstract

Un grafo con dos terminales G es un grafo que posee dos vértices distinguidos en V (G), denominados terminales. Sean n, m y d enteros positivos tales que n ≥ d − 1 y 1 ≤ m ≤ (n+2/2). Sea Td n,m el conjunto de todos los grafos con dos terminales que poseen exactamente n vértices no terminales, m aristas, y la distancia entre sus terminales es igual a d. Sea p un número real en [0, 1] y sea G un grafo con dos terminales en Td n,m. La confiabilidad de G se denota NRG(p) y se define como la probabilidad de que exista un camino entre los terminales de G en el subgrafo de G resultante de remover independientemente a cada uno de sus vértices no terminales con probabilidad 1 − p. Decimos que G es uniformemente más confiable en Td n,m si para todo H en Td n,m y todo p en [0, 1] se cumple que NRG(p) ≥ NRH(p). En trabajos previos se ha logrado caracterizar la existencia e inexistencia de grafos con dos terminales uniformemente más confiables en cada clase no vacía Td n,m cuando d es no mayor que 3. Brown et al. [Networks 76(3):414-426, 2020] conjeturaron que no existe ningún grafo con dos terminales uniformemente más confiable en Td n,m cuando d ≥ 4, n ≥ 2(d − 1) y 2d ≤ m ≤ (d − 2)⌊n /(d−1)⌋2 + ⌊n /d−1⌋ − 1. El objetivo de este proyecto de grado es analizar si la conjetura de Brown et al. es correcta cuando d = 4. Por un lado, se determinan propiedades inherentes a todos los grafos con dos terminales que son localmente más confiables en T4n,m cuando p es próximo a 1. Por otro lado, se demuestra que ninguno de dichos grafos con dos terminales es localmente más confiable cuando p es próximo a 0. Para llevar a cabo esta segunda fase se desarrolla una metodología novedosa basada en programación no lineal entera. Dicha metodología permite probar que la conjetura de Brown es cierta cuando d = 4, excepto en aquellos pares de enteros n y m tales que n ≥ 9 y m = 11. En dichos casos, se han desarrollado programas que permiten realizar un estudio computacional exhaustivo. Dicho estudio basado en asistencia computacional permite confirmar que la conjetura de Brown es correcta cuando d = 4.