Remarks on the Complexity of Signed k-Domination on GraphsReport as inadecuate




Remarks on the Complexity of Signed k-Domination on Graphs - Download this document for free, or read online. Document in PDF available to download.

This paper is motivated by the concept ofthe signed k-domination problem and dedicated to the complexity of the problemon graphs. For any fixed nonnegative integer k, we show that the signed k-dominationproblem is NP-complete for doubly chordal graphs. For strongly chordal graphsand distance-hereditary graphs, we show that the signed k-domination problemcan be solved in polynomial time. We also show that the problem is linear-timesolvable for trees, interval graphs, and chordal comparability graphs.

KEYWORDS

Graph Algorithm, Signed k-Domination, Strongly Chordal Graph, Tree, Fixed Parameter Tractable

Cite this paper

Lee, C. , Lo, C. , Ye, R. , Xu, X. , Shi, X. and Li, J. 2015 Remarks on the Complexity of Signed k-Domination on Graphs. Journal of Applied Mathematics and Physics, 3, 32-37. doi: 10.4236-jamp.2015.31005.





Author: Chuan-Min Lee1, Cheng-Chien Lo1, Rui-Xin Ye2, Xun Xu2, Xiao-Han Shi2, Jia-Ying Li2

Source: http://www.scirp.org/



DOWNLOAD PDF




Related documents