Valid inequalities and complete characterizations of the 2-domination and the P3-hull number polytopes.

Given a graph G = (V, E), a subset S ⊆ V is 2-dominating if every vertex in S¯ has at least two neighbors in S. The minimum cardinality of such a set is called the 2-domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S , at each step marks all unmarked vertices having two previously marked neighbors. In such a process, the minimum number of initial vertices in S such that eventually all vertices are marked is called the P 3 -hull number of G. These parameters are relevant both as a generalization of the domination number and in the context of discrete convexities in graphs, particularly the P 3 convexity. In this work, we explore a polyhedral relation between these two parameters and, in addition, we provide new families of valid inequalities for the associated polytopes. Finally, we give explicit descriptions of the polytopes associated to these problems when G is a path, a cycle, or a complete graph. If G is a tree we give the complete description of the associated 2-domination polytope. [ABSTRACT FROM AUTHOR]