k-tuple domination in graphs

被引：71

作者：

Liao, CS

Chang, GJ ^{[1
]}

机构：

[1] Natl Taiwan Univ, Dept Math, Taipei 106, Taiwan

[2] Acad Sinica, Inst Informat Sci, Taipei 115, Taiwan

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 87卷 / 01期

关键词：

algorithms; k-tuple domination; domination; strongly chordal graph; chordal graph; split graph; bipartite graph;

D O I：

10.1016/S0020-0190(03)00233-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：45 / 50

页数：6

共 23 条

[1] CHARACTERIZATIONS OF TOTALLY BALANCED MATRICES [J].