Propiedades de las facetas del poliedro de 2-dominación de ciclos

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

Cordoba

Congreso; IV Congreso latinoamericano de Matemáticos; 2012

CLAM

Dado un grafo G=(V,E) y un entero k, un conjunto k-dominante de G es un conjunto S\subset V, tal que |S\cap N[i]| \geq k para todo i\in V, donde N[i] es la vecindad cerrada de I, es decir, el conjunto que contiene a I y a los vÉrtices de G adyacentes a I. Si \gamma _k(G) es el mínimo cardinal de un conjunto k-dominante de G, es inmediato observar que $ \gamma _k(G)=\min\{\mathbf 1x:\; N(G)x\geq \mathbf 1 k, \; x\in \{0,1\}^{|V|}\}, $ donde \mathbf 1 es el vector con todas sus entradas iguales a 1 y N(G) es la matriz de incidencia de las vecindades cerradas de los vértices de G. Se define el poliedro de k-dominación de G como $ P^{*}_k(G)=\{ x\in \{0,1\}^{|V|}, N(G)x\geq \mathbf 1 k\}. $ M. Bouchakour et al. determinan todas las desigualdades que definen faceta para P^{*}_1(G) en el caso particular en que el grafo sea un ciclo C_n, y prueban que las mismas pueden separarse en tiempo polinomial. Por otro lado, en un trabajo anterior se describe completamente el poliedro P^{*}_2(C_n). En este trabajo veremos que las desigualdades que definen faceta para P^{*}_2(C_n) obtenidas pueden separarse en tiempo polinomial.