PROPIEDADES MATEMÁTICO-COMPUTACIONALES ASOCIADAS A PROBLEMAS DE TEORÍA DE DOMINACIÓN

Esta tesis aborda el estudio de la Teoría de Dominación en Grafos, centrándose en las propiedades matemático-computacionales de diversos problemas de dominación y el desarrollo de algoritmos eficientes para su resolución. Los problemas tratados incluyen el problema del conjunto dominante, el conjunto dominante global, el conjunto dominante global total y el conjunto k-dominante global total. Un conjunto dominante de un grafo es un subconjunto de vértices tal que todo vértice no perteneciente a dicho conjunto es adyacente a al menos un vértice del conjunto. Un conjunto dominante global es un conjunto que domina tanto al grafo como a su complemento. Un conjunto dominante global total es un conjunto donde cada vértice del grafo es adyacente a al menos un vértice del conjunto, incluidos los vértices del conjunto mismo, tanto en el grafo como en su complemento. Finalmente, un conjunto kdominante global total requiere que cada vértice del grafo sea adyacente a al menos k vértices del conjunto en el grafo y su complemento.