Simple algorithms to compute $k$-tuple total dominaing sets and $k$-tuple dominating sets
Sharareh Alipour, Amir Jafari · 2017
Let $G$ be a connected graph of order $n$, whose minimum vertex degree is at least $k$. A subset $S$ of vertices in $G$ is a $k$-tuple total dominating set if every vertex of $G$ is adjacent to at least $k$ vertices in S. The minimum cardinality of a $k$-tuple total dominating set of $G$ is the $k$-tuple total domination number of $G$, denoted by $\gamma_{\times k,t}(G)$. Henning and Yeo in \cite{hen} proved that if $G$ is a cubic graph different from the Heawood graph, $\gamma_{\times 2, t}(G) \leq \frac{5}{6}n$, and this bound is sharp. Similarly, a $k$-tuple dominating set is a subset $S$ of vertices of $G$, $V (G)$ such that $|N[v] \cap S| \geq k$ for every vertex $v$, where $N[v] = \{v\}\cup \{u \in V(G) : uv \in E(G)\}$. The $k$-tuple domination number of $G$, denoted by $\gamma_{\times k}(G)$, is the minimum cardinality of a $k$-tuple dominating set of $G$. In this paper, we give a simple approach to achieve the same upper bounds and also improve the upper bounds in some special cases. For example, we show that for a $r$-regular graph $G$ of order $n$, with $r\ge k$, $\gamma_{\times k}(G)\le \frac{r^2}{r^2+1}n$. In addition, our method gives algorithms to compute dominating sets of small size, while the previous methods are existential.