k-tuple domination in graphs |
| |
Authors: | Chung-Shou Liao |
| |
Affiliation: | a Institute of Information Sciences, Academia Sinica, Nankang, Taipei 115, Taiwan b Department of Mathematics, National Taiwan University, Taipei 106, Taiwan |
| |
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 in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs. |
| |
Keywords: | Algorithms k-tuple domination Domination Strongly chordal graph Chordal graph Split graph Bipartite graph |
本文献已被 ScienceDirect 等数据库收录! |
|