Generalized perfect domination in graphs

作者：Chaluvaraju B; Vidya K A^*

来源：Journal of Combinatorial Optimization, 2014, 27(2): 292-301.

DOI：10.1007/s10878-012-9510-y

• k-Domination
• Perfect k-domination
• NP-Completeness
• Dynamic programming

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number gamma (kp) (G). In this paper, we give characterizations of graphs for which gamma (kp) (G)=gamma(G)+k-2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.

• 出版日期2014-2