Análisis y mejora de parámetros de dominación, conectividad y fiabilidad en redes modeladas por grafos sujetos a propiedades estructurales

Resumen

Podemos ubicar los temas de estudio abordados en esta tesis dentro de la Teoría de Grafos. En concreto, y principalmente, en el estudio de la vulnerabilidad de una red, modelada mediante un grafo finito, aplicando diferentes estrategias de defensa y protección de los grafos. Estos problemas son tratados, de manera natural, en áreas de investigación de dicha teoría tales como la conectividad, la dominación en grafos y sus muchas variantes. En la primera parte de esta memoria de tesis hemos abordado el estudio de la vulnerabilidad de una red en la que se consideran ciertas probabilidades de fallo, distintas e independientes, tanto en vértices como en aristas. Para ello, se estiman diversas cotas del parámetro que denominaremos "conectividad residual". Este parámetro nos servirá para conocer la probabilidad de que los elementos que permanezcan activos tras un cierto lapso de tiempo, en el que determinados vértices y aristas dejan de funcionar en la red, induzcan un grafo conexo. En el mismo sentido, la dominación romana es un campo de estudio, dentro de la dominación en grafos, muy relacionado con la medida de la fiabilidad de una red, que ha recibido gran atención en las últimas décadas. La dominación romana se plantea como estrategia defensiva de los vértices de un grafo y a partir de ella se han desarrollado numerosas variaciones. Comenzamos analizando el efecto de la contracción de aristas sobre la dominación romana y algunas de sus variantes. En esta tesis definimos y estudiamos los parámetros número de contracción de la dominación romana, de la dominación romana total y de la dominación romana mixta. En particular, para la dominación romana estudiamos este nuevo parámetro en ciertas familias de grafos, siendo de especial mención los resultados obtenidos para árboles de diámetro menor o igual a cinco. De la dominación romana se han derivado diversas variantes bien por la modificación de alguna propiedad o por la forma en que se dominan los vértices. No obstante en la mayoría de ellas se considera que el grafo puede ser atacado de forma individual y a uno solo de sus elementos, generalmente un vértice. Actualmente la capacidad de ataque a una red es mucho más amplia, por lo que la protección planteada hasta ahora puede no ser suficiente. Hemos abordado tal cuestión desde dos puntos de vista. En primer lugar hemos planteado la protección de un grafo ante ataques múltiples y simultáneos a distintos vértices, hasta ahora nunca hecho, lo que nos ha llevado a definir una nueva variante de la dominación romana, la dominación romana fuerte y el parámetro número de dominación romana fuerte. En su estudio hemos establecido cotas de dicho parámetro respecto a invariantes estructurales y en relación con otras dominaciones. Ante un ataque individual a un vértice, la idea de reforzar la dominación romana la proponen, en 2016, Beeler y otros [22], donde definen la dominación romana doble. Este otro punto de vista ha dado lugar a la introducción del concepto de la [k]-dominación romana y al estudio más profundo de un nuevo caso particular, introducido en esta tesis, la dominación romana triple. De su análisis se han derivado los primeros resultados sobre el número de dominación romana triple en cuanto a su relación con otras dominaciones.