For a fixed positive integer $k$ and $G=(V, E)$ a connected graph of order $n$, whose minimum vertex degree is at least $k$, a set $S\subseteq V$ is a total $k$-dominating set, also known as a $k$-tuple total dominating set, if every vertex $v\in V$ has at least $k$ neighbors in $S$. The minimum size of a total $k$-dominating set for $G$ is called the total $k$-domination number of $G$, denoted by $\gamma_{kt}(G)$. The total $k$-domination problem is to determine a minimum total $k$-dominating set of $G$. Since the exact problem is in general quite difficult to solve, it is also of interest to have good upper bounds on the total $k$-domination number. In this paper, we present a probabilistic approach to computing an upper bound for the total $k$-domination number that improves on some previous results.
domination, $k$-tuple total domination, probabilistic method
05C30, 05C65, 05C69