On $k$-tuple and $k$-tuple total domination numbers of regular graphs

Abstract

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)\le \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|\ge 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 compute an upper bound for $(r-1)$-tuple total domination number of $r$-regular graphs. Also, we give an upper bound for the $r$-tuple dominating number of $r$-regular graphs. In addition, our method gives algorithms to compute dominating sets with the given bounds, while the previous methods are existential.