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

Authors

  • Lyle Leon Butanas Department of Mathematics and Statistics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines
  • Mhelmar Labendia Department of Mathematics and Statistics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines
  • Karlo Orge Department of Mathematics and Statistics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines

Keywords:

INLP formulation, paired dominating set, twin paired dominating set, paired restrained dominating set, outer paired dominating set

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$.

Downloads

Published

2024-05-31

How to Cite

Butanas, L. L., Labendia, M., & Orge, K. (2024). Integer Nonlinear Programming Formulation for some Variations of Paired Domination in Multigraphs without Loops. The Mindanawan Journal of Mathematics, 6(1), 47–65. Retrieved from https://journals.msuiit.edu.ph/tmjm/article/view/423

Issue

Section

Articles