%0 Journal Article
%T Remarks on the Complexity of Signed k-Domination on Graphs
%A Chuan-Min Lee
%A Cheng-Chien Lo
%A Rui-Xin Ye
%A Xun Xu
%A Xiao-Han Shi
%A Jia-Ying Li
%J Journal of Applied Mathematics and Physics
%P 32-37
%@ 2327-4379
%D 2015
%I Scientific Research Publishing
%R 10.4236/jamp.2015.31005
%X <p class=\"MsoNormal\">
	<span lang=\"EN-US\">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.</span>
</p>
%K Graph Algorithm
%K Signed k-Domination
%K Strongly Chordal Graph
%K Tree
%K Fixed Parameter Tractable
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=53574