Back
 JAMP  Vol.3 No.1 , January 2015
Remarks on the Complexity of Signed k-Domination on Graphs
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.
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.
References

[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. http://dx.doi.org/10.1016/j.disc.2007.08.080

[4]   Lee, C.-M. (2014) Remarks on the Complexity of Non-negative Signed Domination. Journal of Networks, 9, 2051- 2058. http://dx.doi.org/10.4304/jnw.9.8.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. http://dx.doi.org/10.1137/S0895480193253415

[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. http://dx.doi.org/10.1016/S0168-0072(95)00020-8

[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. http://dx.doi.org/10.1002/net.3230230108

[9]   Rose, D.J. (1970) Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications, 32, 597-609. http://dx.doi.org/10.1016/0022-247X(70)90282-9

[10]   Farber, M. (1983) Characterizations of Strongly Chordal Graphs. Discrete Mathematics, 43, 173-189. http://dx.doi.org/10.1016/0012-365X(83)90154-1

[11]   Paige, R. and Tarjan, R.E. (1987) Three Partition Refinement Algorithms. SIAM Journal on Computing, 16, 973-989. http://dx.doi.org/10.1137/0216062

[12]   Spinrad, J.P. (1993) Doubly Lexical Ordering of Dense 0-1 Matrices. Information Processing Letters, 45, 229-235. http://dx.doi.org/10.1016/0020-0190(93)90209-R

[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. http://dx.doi.org/10.1137/1.9780898719796

[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. http://dx.doi.org/10.1137/0213035

[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. http://dx.doi.org/10.1016/S0022-0000(76)80045-1

[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. http://dx.doi.org/10.1016/S0166-218X(98)00137-1

[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. http://dx.doi.org/10.1016/S0020-0190(03)00228-X

[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.

 
 
Top