Dominación romana en grafos

Abstract

El Problema de Dominación Romana fue formalizado por Cockayne et al. Allí, se modeliza el problema del emperador Constantino utilizando la Teoría de Grafos. Se sabe que el Problema de Dominación Romana es NP-completo en general. En esta tesina abordaremos el análisis de la complejidad del problema cuando nos restringimos a ciertas familias de grafos. Entre las familias de grafos a estudiar, están aquellas que se pueden definir por tener una cantidad restringida de P4’s en un sentido local. La estrategia de abordaje para el problema es descomponer el grafo en subgrafos más pequeños, mediante ciertas operaciones. Si conocemos el comportamiento del parámetro γR bajo estas operaciones y podemos calcular el valor del parámetro para estos subgrafos mas pequeños, y todo esto lo podemos hacer en tiempo polinomial, entonces podemos recuperar el valor del número de dominación romana en el grafo original. Parte de los resultados presentados en esta tesina fueron presentados en XIII Jornada de Ciencia y Tecnología: Divulgación de la Producción Científica y Tecnológica de la Universidad Nacional de Rosario (2019); y en LXIX Reunión de Comunicaciones Científicas de la Reunión Anual Virtual de la Unión Matemática Argentina (virtUMA 2020).