On the k-dominating set polytope on web graphs

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

Simposio; 2010 (International Symposium in Combinatorial Optimization); 2010

In this work we present some results on the polyhedral structure of the convex hull of integer points in polyhedra of the form {x >=0 : Mx >=k1}, for a 0, 1 matrix M and a positive integer number k. In particular, we consider the k-dominating set problem in a graph. Given a graph G = (V,E), a set D of nodes is a k-dominating set if every vertex in V is adjacent to at least k vertices of D. The k-dominating set problem consists in finding a k-dominating set of minimum cardinality. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G and it is a natural generalization of the well-known dominating set polytope of a graph. We apply our results for general problems to the k-dominating set polytope of some particular families of web graphs.