Conjunto Dominante Total Outer k-independiente en Gráficas

Ponente(s): Ernesto Parra Inza, Juan Carlos Hernández Gómez, José María Sigarreta Almira.

Un conjunto de vértices $S$ de un gráfica $G(V,E)$ es un conjunto dominante total si cada vértice de $G$ es adyacente al menos a un vértice en $S$. Decimos que un conjunto dominante total $S$ es un conjunto dominante total \textit{outer} $k$-independiente de $G$ si el grado máximo del subgrafo inducido por los vértices que no están en $S$ es menor o igual a $k-1$. La cardinalidad mínima entre todos los conjuntos dominantes totales \textit{outer} $k$-independientes de $G$ es el número de dominación total \textit{outer} $k$-independiente de $G$. En este trabajo se introduce dicho parámetro y se comienza el estudio de sus propiedades combinatorias y computacionales. Se demuestra que el cálculo del número de dominación total \textit{outer} $k$-independientes de $G$ es un problema NP-\textit{hard} y se propone un algoritmo computacional para encontrar una aproximación del mismo. Además se brinda un Modelo de Programación Lineal Entera que encuentra un conjunto dominante total \textit{outer} $k$-independiente mínimo de $G$.