Propiedades del Número de k-Dominación Total Global en Grafos

Ponente(s): Ernesto Parra Inza, José M. Sigarreta Almira; Nodari Vakhania

Un subconjunto no vacío D ⊂ V de vértices de un grafo G = (V, E) es un conjunto dominante si cada vértice de este grafo es adyacente al menos a un vértice de este conjunto, excepto los vértices que pertenecen a este conjunto. D ⊆ V es un conjunto k-dominante total si hay al menos k vértices del conjunto D adyacentes a cada vértice v ∈ V, y es un conjunto k-dominante total global si D es un conjunto k-dominante total tanto de G como de su grafo complemento. El número de k-dominación total global de G es la cardinalidad mínima de los conjuntos k-dominante total global de G, a estos conjuntos los denotaremos GTkD-set. Encontrar el valor de este parámetro es un problema NP-hard. En este trabajo se proponen límites superior e inferior para el número de k-dominación total global de G y se desarrolla un método que genera un GTkD-set a partir de un GT(k - 1)D-set para valores de k sucesivamente crecientes.