Variaciones del problema de dominación en grafos definidos por subgrafos prohibidos de a los sumo cuatro vértices

GABRIELA ARGIROFFO; LARA FERNANDEZ; PABLO TORRES

Rosario

Jornada; XII Jornada de Ciencia y Tecnología; 2018

Universidad Nacional de Rosario

El problema de dominación en un grafo G = (V, E) consiste en hallar una función f de V en {0,1} de peso mínimo que satisfaga que, para todo i en V, la suma de los f(j) con j en N[i] sea por lo menos 1, donde N[i] son los vértices de G a distancia a lo sumo 1 de i. En este trabajo consideramos las dos variaciones de este problema. El problema de k-tupla dominante (problema de {k}-dominación) en un grafo: dado k natural, se pretende hallar una función f de V en {0, 1} (respectivamente, en {0, 1, ..., k}) de peso mínimo y tal que para todo i en V, la suma de los f(j) con j en N[i] sea por lo menos k. Dado un entero no negativo k, se consideran los siguientes problemas de decisión:Problema de k-upla dominante (k-DOM): Dados G = (V, E), j en N, ¿admite G una función de k-upla dominante de peso a lo sumo j?Problema de {k}-dominación ({k}-DOM): Dados G = (V, E), j en N, ¿admite G una función de {k}-dominación de peso a lo sumo j?Estos problemas son NP-completos desde el punto de vista de la complejidad computacional.Recientemente, Min Chih Lin y Michael Mizrahi estudian el problema de dominación DOM en familias de grafos definidas por subgrafos inducidos prohibidos de a lo sumo cuatro vértices, es decir, si el grafo es F-free, donde F es un conjunto de grafos de a lo sumo cuatro vértices.En este trabajo abordamos el estudio de la complejidad computacional de los problemas k-DOM y {k}-DOM para grafos F-free, donde F es un conjunto de grafos de a lo sumo cuatro vértices.