Computational Complexity of Domination Integrity in Graphs

Abstract

In a graph G, those dominating sets S which give minimum value for |S| + m G−S , where m G−S denotes the maximum order of a component of G−S, are called dominating integrity sets of G briefly called DI-sets of G . This concept combines two important aspects namely domination and integrity in graphs. In this paper, we show that the decision problem domination integrity is NP-complete even when restricted to planar or chordal graphs.

Keywords

• Integrity,Domination Integrity

References

1. Barefoot,C.A., Entringer,R. and Swart,H.C., (1987), Vulnerability in graphs A comparative survey, J. Combin. Math. Combin. Comput. 1, pp. 1322.
2. Barefoot,C.A.,(1989), On the vulnerability of graphs, Ph.D. thesis, University of Natal, Durban. S.A. [3] Barefoot,C.A., Entringer,R. and Swart,H.C., (1987), Integrity of trees and powers of cycles, Congress. Numer., 58, pp. 103114.
3. Bagga,K.S., Beineke,L.W., Lipman,M.J. and Pippert,R.E.,(1992), Edge-integrity: a survey,Discrete Mathematics, 124, pp. 3-12.
4. Bagga,K.S., Beineke,L.W., Goddard,W.D., Lipman,M.J. and Pippert,R.E.(1992), A survey of in- tegrity, Discrete Appl. Math., 37/38, pp. 13-28.
5. Bermond,J.C and Peyrat,C., (1989), De Bruijn and Kautz networks: a competitor for the hypercube, in: F. Andr, J.P. Verjus (Eds.), Hypercube and Distributed Computers, Elsevier/North- Holland, Amsterdam.
6. Randerath,B. Volkmann,L.,(1998), Characterization of graphs with equal domination and covering number, Discrete Mathematics, 191, pp. 159-169.
7. Cockayne,E.J. and Hedetniemi,S.T. (1977), Towards a theory of domination in Graphs, Networks 7, pp. 247-261.
8. Choudum,S.A. (1999), Discrete Optimization Problems in the Design of Interconnection Networks, DST project Report.

9. Choudum,S.A, (2002), Augmented Cubes, Networks, Vol.40(2), pp. 71-84.
10. Garey,M. R. and Johnson,D.S,(1979), Computers and Interactability :A Guide to the theory of NP-completeness,Freeman.
11. Goddard,W. and Swart,H.C., (1988), On the Integrity of combinations of graphs, J. Combin.Math. Combin. Comput., 7, pp. 3-18.
12. Goddard,W., Swart,H.C., (1990), Integrity in graphs : Bounds and Basics, Journal of Combin.Math. Combin. Comput., 7, pp. 139-151.
13. Lane,H.C., Entringer,R.C. and Fellows,M.R., (1987) Computational Complexity of Integrity,J. Com- bin. Math. Combin. Comput, 2 , pp. 179-191.
14. Sundareswaran,R. and Swaminathan,V., Domination Integrity of graphs, Proceedings of International Conference on Mathematical and Experimentals of Physics.
15. Haynes,T.W., Hedetniemi,S.T. and Slater,P.J., (1998), Fundamentals of Domination in Graphs, Mar- cel Dekker Inc.
16. Haynes,T.W., Hedetniemi,S.T. and Slater,P.J.,(1998), Domination in Graphs: Advanced Topics, Mar- cel Dekker Inc.
17. R.Sundareswaran for the photography and short autobiography, see TWMS J. App. Eng. Math., V.5, N.1.
18. V.Swaminathan for the photography and short autobiography, see TWMS J. App. Eng. Math., V.5, N.1.