The 2-dominating set polytope of cycles and related graph classes

Given a graph G and a nonnegative integer number k, a k-dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least k elements of D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we present a complete description of the 2-dominating set polytope of cycles and show that every facet of this polytope can be separated in polynomial time. We use our findings to derive facets of the 2-dominating set polytope of cacti, i.e. graphs obtained as 1-sums of cycles and edges.