Share This Article:

Remarks on the Complexity of Signed k-Domination on Graphs

Abstract Full-Text HTML XML Download Download as PDF (Size:265KB) PP. 32-37
DOI: 10.4236/jamp.2015.31005    3,546 Downloads   4,024 Views  


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.

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Wang, C. (2012) The Signed k-Domination Numbers in Graphs. Ars Combinatoria, 106, 205-211.
[2] Hattingh, J.H., Henning, M.A. and Slater, P.J. (1995) The Algorithmic Complexity of Signed Domination in Graphs. Australasian Journal of Combinatorics, 12, 101-112.
[3] Lee, C.-M. and Chang, M.-S. (2008) Variations of Y-Dominating Functions on Graphs. Discrete Mathematics, 308, 4185-4204.
[4] Lee, C.-M. (2014) Remarks on the Complexity of Non-negative Signed Domination. Journal of Networks, 9, 2051- 2058.
[5] Brandst?dt, A., Dragan, F.F., Chepoi, V.D. and Voloshin, V. (1998) Dually Chordal Graphs. SIAM Journal on Discrete Mathematics, 11, 437-455.
[6] Cai, L., Chen, J., Downey, R.G. and Fellows, M.R. (1997) Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic, 84, 119-138.
[7] Downey, R.G. and Fellows, M.R. (1999) Parameterized Complexity. Monographs in Computer Science, Springer- Verlag.
[8] Moscarini, M. (1993) Doubly Chordal Graphs, Steiner Trees, and Connected Domination. Networks, 23, 59-69.
[9] Rose, D.J. (1970) Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications, 32, 597-609.
[10] Farber, M. (1983) Characterizations of Strongly Chordal Graphs. Discrete Mathematics, 43, 173-189.
[11] Paige, R. and Tarjan, R.E. (1987) Three Partition Refinement Algorithms. SIAM Journal on Computing, 16, 973-989.
[12] Spinrad, J.P. (1993) Doubly Lexical Ordering of Dense 0-1 Matrices. Information Processing Letters, 45, 229-235.
[13] Brandst?dt, A., Le, V.B. and Spinrad, J.P. (1999) Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia 1999.
[14] Tarjan, R.E. and Yannakakis, M. (1984) Simple Linear Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Joural on Computing, 13, 566-579.
[15] Booth, S. and Lueker, S. (1976) Testing for the Consecutive Ones Property, Interval Graphs, Graph Planarity Using PQ-Trees Algorithms. Journal of Computer and System Sciences, 13, 335-379.
[16] Borie, R.B. and Spinrad, J.P. (1999) Construction of a Simple Elimination Scheme for a Chordal Comparability Graph in Linear Time. Discrete Applied Mathematics, 91, 287-292.
[17] Sawada, J. and Spinrad, J.P. (2003) From a Simple Elimination Ordering to a Strong Elimination Ordering in Linear Time. Information Processing Letters, 86, 299-302.
[18] Chang, M.-S., Hsieh, S.-Y. and Chen, G.-H. (1997) Dynamic Programming on Distance-Hereditary Graphs. Proceedings of the 8th International Symposium o Algorithms and Computation, Lecture Notes in Computer Science, Vol. 1350, 344-353.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.