Cotas para el numero de k-upla dominacion en una subclase de grafos ´ arco-circulares

ESCALANTE, MARIANA SILVINA; LOPEZ PUJATO, MARIA INES; LEONI, VALERIA ALEJANDRA

Rosario(virtual)

Congreso; VirtUMA 2021; 2021

Unión Matemática Argentina

Dado un grafo G = (V; E) y un entero positivo k, decimos que D ⊆ V es un conjunto k-upla dominante en G, si en la vecindad cerrada de cada vértice de G hay al menos k elementos de D. Denotamos porγ×k(G) el tamaño de un conjunto k-upla dominante de mínimo cardinal en G. El problema de la k-upla dominación consiste en hallar un conjunto k-upla dominante en G de tamaño γ×k(G) [4].Desde el punto de vista de la complejidad computacional, este problema (para cada k fijo) es NP-díficil [6]. Sin embargo, sobre la familia de los grafos arco-circulares no se conoce su complejidad para k ≥ 2 y para k = 1 existe un algoritmo que permite resolver el problema en tiempo polinomial [5]. Es por lo que resulta de interés analizar familias de grafos arco-circulares con una estructura particular que nos permita avanzar sobre el estudio de este problema. En trabajos previos se encontró un algoritmo eficiente que resuelve el problema en la subclase de los grafos co-biconvexos, para valores de k acotados por cierto parámetro en función del grafo de entrada. Siguiendo esta línea de investigación, se estudió la familia de los grafos web, obteniendo un algoritmo que en tiempo lineal encuentra un conjunto k-upla dominante mínimo y el número de k-upla dominación para todo grafo web y todo valor de k. En la presente comunicación abordamos el problema de la k-upla dominación para todos los enteros positivos k en otra subclase de grafos arco-circulares, no comparable con las ya estudiadas, que denominamos grafos cuasi-web. En primer lugar, analizamos las propiedades estructurales de esta familia de grafos. Luego, basándonos en una formulación de este problema como programa lineal entero, consideramos desigualdades válidas para la cápsula convexa de las soluciones factibles en él, llamado el poliedro de k-upla dominación. Utilizando la matriz de vecindades cerradas de los grafos cuasi-web que definen estas desigualdades, hallamos cotas inferiores ajustadas para γ×k(G), para todo grafo cuasi-web G y todo entero positivo k.