Integer Nonlinear Programming Formulation for some Variations of Paired Domination in Multigraphs without Loops
The Mindanawan Journal of Mathematics · 31.05.2024 · 6 (1) · 47
DOI: 10.62071/tmjm.v6i1.423 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Mindanawan Journal of Mathematics, online erschienen am 31.05.2024. Verfasst von Lyle Leon Butanas und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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$.
Zitieren
APA
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. https://doi.org/10.62071/tmjm.v6i1.423
Vancouver
Butanas LL, Labendia M, Orge K. Integer Nonlinear Programming Formulation for some Variations of Paired Domination in Multigraphs without Loops. The Mindanawan Journal of Mathematics. 2024;6(1):47. doi:10.62071/tmjm.v6i1.423
BibTeX
@article{Butanas2024,
author = {Butanas, Lyle Leon and Labendia, Mhelmar and Orge, Karlo},
title = {Integer Nonlinear Programming Formulation for some Variations of Paired Domination in Multigraphs without Loops},
journal = {The Mindanawan Journal of Mathematics},
year = {2024},
volume = {6},
number = {1},
pages = {47},
doi = {10.62071/tmjm.v6i1.423}
}
EUVIMED