Avances en la caracterización del politopo de 2-dominación de cactus

ARGIROFFO, GABRIELA; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA

Rosario

Congreso; LXII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2013

Unión Matemática Argentina

Dado un grafo G=(V,E) y un entero k, un conjunto k-dominante de G es un conjunto S contenido en V, tal que tiene al menos k elementos en común con toda vecindad cerrada de un nodo. Para abordar el tratamiento desde el punto de vista poliedral de este problema, definimos el poliedro de k-dominación de G y encontramos la descripción completa del poliedro de 2-dominación sobre la familia de los ciclos. En este trabajo, nos centramos en el estudio del politopo de 2-dominación de la familia de grafos llamados cactus, definidos como aquellos obtenidos por 1-sumas de ciclos y aristas. En particular, se estudia el politopo de 2-dominación de árboles y se obtiene la descripción completa del mismo en el caso de grafos langosta. Por otro lado, se avanzó en la caracterización del politopo de 2-dominación de cactus con ciclos y se consiguió la descripción completa del politopo de 2-dominación de ciertas subfamilias de estos, ampliando resultados obtenidos en un trabajo previo.