A polyhedral view to a generalization of multiple domination.

Given an undirected simple graph G = (V , E) and integer values f v , v ∈ V , a node subset D ⊆ V is called an f -tuple dominating set if, for each node v ∈ V , its closed neighborhood intersects D in at least f v nodes. We study the polytope that is defined as the convex hull of the incidence vectors in R V of the f -tuple dominating sets in G. New families of valid inequalities are introduced and a complete formulation is given for the case of stars. A corollary of our results is a proof that the conjecture reported in Argiroffo (2013) on a complete formulation of the 2-tuple dominating set polytope of trees does not hold. Preliminary computational results are also reported. [ABSTRACT FROM AUTHOR]