Integer Nonlinear Programming Formulation for some Variations of Paired Domination in Multigraphs without Loops

Abstract

In this paper, we construct integer programming formulations for the paired, twin paired, paired restrained, and outer paired dominating set problems.

Let $G$ be a multigraph. A set $S\subseteq V(G)$ is called a \textit{paired dominating set} (resp., an \textit{outer paired dominating set}) if it is a dominating set in $G$ and $\langle S\rangle$ (resp., $\langle S^c\rangle$) contains at least one perfect matching. The \textit{paired domination number} $\gamma_p(G)$ (resp., \textit{outer paired domination number} $\gamma_{op}(G)$) is defined to be the minimum cardinality of a paired (resp., an outer paired) dominating set $S$ in $G$. Moreover, a set $S\subseteq V(G)$ is called a \textit{twin paired dominating set} (resp., \textit{paired restrained dominating set}) in $G$ if $S$ is a paired dominating set and $\langle S^c\rangle$ contains a perfect matching (resp., contains no isolated vertex). The \textit{twin paired domination number} $\gamma_{tp}(G)$ (resp., \textit{paired restrained domination number} $\gamma_{pr}(G)$) is defined to be the minimum cardinality of a twin paired (resp., paired restrained) dominating set $S$ in $G$.