TITLE:
Remarks on the Complexity of Signed k-Domination on Graphs
AUTHORS:
Chuan-Min Lee, Cheng-Chien Lo, Rui-Xin Ye, Xun Xu, Xiao-Han Shi, Jia-Ying Li
KEYWORDS:
Graph Algorithm, Signed k-Domination, Strongly Chordal Graph, Tree, Fixed Parameter Tractable
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.3 No.1,
January
28,
2015
ABSTRACT:
This paper is motivated by the concept of
the signed k-domination problem and dedicated to the complexity of the problem
on graphs. For any fixed nonnegative integer k, we show that the signed k-domination
problem is NP-complete for doubly chordal graphs. For strongly chordal graphs
and distance-hereditary graphs, we show that the signed k-domination problem
can be solved in polynomial time. We also show that the problem is linear-time
solvable for trees, interval graphs, and chordal comparability graphs.