On the K-Dominating Set Polytope of a Cycle

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

Rosario, Argentina

Congreso; II Congreso de Matemática Aplicada, Computacional e Industrial; 2009

Siam-Argentina

In this work we present some results on the polyhedral structure of the convex hull of integer solutions in general polyhedra of the form {x >=0: Mx >=k }, for a 0,1 matrix M.Given a graph G=(V,E) and k in  Z_+,  we also consider the problem of finding a k-dominating set in G, that is, a subset D of V such that every vertex in V is adjacent to at least k vertices of D. The emph{k-dominating set polytope} is the convex hull of the incidence vectors of k-dominating sets in G, or equivalently, the convex hull of the 0,1 solutions in {x >= 0: N[G] x >=k}, where N[G] is the closed neighborhood matrix of G. This is a natural generalization of the well-known dominating set polytope in graphs (for k=1). We apply our results for general problems to the k-dominating set polytope. Finally, using a linear transformation and results on web graphs, we give the complete description of the 2-dominating set polytope in a cycle C_n, for n >= 6.