Algorithmic aspect of k-tuple domination in graphs

Abstract

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset such that every vertex in the graph is dominated by at least k vertices in this set. The present paper studies the k-tuple domination problem in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the 2-tuple domination problem in trees by employing a labeling method.