It is a well-known fact that finding a minimum dominating set and consequently finding the $k$-tuple dominating set of a general graph is an NP-complete problem. In this paper, we first model these problems as nonlinear binary optimization problems and then extract two semidefinite relaxations.
