Computational Complexity of Domination Integrity in Graphs

Year 2015, Volume: 5 Issue: 2, 214 - 218, 01.12.2015

- R.sundareswaran - V.swaminathan

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

• Barefoot,C.A., Entringer,R. and Swart,H.C., (1987), Vulnerability in graphs A comparative survey, J. Combin. Math. Combin. Comput. 1, pp. 1322.
• 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.
• Bagga,K.S., Beineke,L.W., Lipman,M.J. and Pippert,R.E.,(1992), Edge-integrity: a survey,Discrete Mathematics, 124, pp. 3-12.
• 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.
• 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.
• Randerath,B. Volkmann,L.,(1998), Characterization of graphs with equal domination and covering number, Discrete Mathematics, 191, pp. 159-169.
• Cockayne,E.J. and Hedetniemi,S.T. (1977), Towards a theory of domination in Graphs, Networks 7, pp. 247-261.
• Choudum,S.A. (1999), Discrete Optimization Problems in the Design of Interconnection Networks, DST project Report.
• Choudum,S.A, (2002), Augmented Cubes, Networks, Vol.40(2), pp. 71-84.
• Garey,M. R. and Johnson,D.S,(1979), Computers and Interactability :A Guide to the theory of NP-completeness,Freeman.
• Goddard,W. and Swart,H.C., (1988), On the Integrity of combinations of graphs, J. Combin.Math. Combin. Comput., 7, pp. 3-18.
• Goddard,W., Swart,H.C., (1990), Integrity in graphs : Bounds and Basics, Journal of Combin.Math. Combin. Comput., 7, pp. 139-151.
• 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.
• Sundareswaran,R. and Swaminathan,V., Domination Integrity of graphs, Proceedings of International Conference on Mathematical and Experimentals of Physics.
• Haynes,T.W., Hedetniemi,S.T. and Slater,P.J., (1998), Fundamentals of Domination in Graphs, Mar- cel Dekker Inc.
• Haynes,T.W., Hedetniemi,S.T. and Slater,P.J.,(1998), Domination in Graphs: Advanced Topics, Mar- cel Dekker Inc.
• R.Sundareswaran for the photography and short autobiography, see TWMS J. App. Eng. Math., V.5, N.1.
• V.Swaminathan for the photography and short autobiography, see TWMS J. App. Eng. Math., V.5, N.1.