Perfect secure domination in graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Vidyavardhaka College of Engineering, Mysuru 570002, Karnataka, India.

2 National Centre for Advanced Research in Discrete Mathematics, Kalasalingam University, Anand Nagar, Krishnankoil-626 126, Tamil Nadu, India.

3 Department of Mathematics, The Catholic University of America, Washington, D.C. 20064, USA.

Abstract

Let $G=(V,E)$ be a graph. A subset $S$ of $V$ is a dominating set of $G$ if every vertex in $V\setminus  S$ is adjacent to a vertex in $S.$ A dominating set $S$ is called a secure dominating set if for each $v\in V\setminus S$ there exists $u\in S$ such that $v$ is adjacent to $u$ and $S_1=(S\setminus\{u\})\cup \{v\}$ is a dominating set. If further the vertex $u\in S$ is unique, then $S$ is called a perfect secure dominating set. The minimum cardinality of a perfect secure dominating set of $G$ is called the perfect  secure domination number of $G$ and is denoted by $\gamma_{ps}(G).$ In this paper we initiate a study of this parameter and present several basic results.

Highlights

Dedicated to Bernhard Banaschewski on the occasion of his 90th birthday

Keywords

References

[1] Burger, A.P., Cockayne, E.J., Grundlingh, W.R., Mynhardt, C.M., van Vuuren, J.H., and Winterbach, W., Finite order domination in graph, J. Combin. Math. Combin. Comput. 49 (2004), 159-175.
[2] Burger, A.P., Cockayne, E.J., Grundlingh, W.R., Mynhardt, C.M., van Vuuren, J.H., and Winterbach, W., Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004), 179-194.
[3] Burger, A.P., Henning, M.A., and van Vuuren, J.H., Vertex covers and secure domination in graphs, Quaest. Math. 31 (2008), 163-171.
[4] Chartrand, G., Lesniak, L., and Zhang, P., "Graphs & Digraphs", Fourth Edition, Chapman and Hall/CRC, 2005.
[5] Cockayne, E.J., Irredundance, secure domination and maximum degree in trees, Discrete Math. 307 (2007), 12-17.
[6] Cockayne, E.J., Favaron, O., and Mynhardt, C.M., Secure domination, weak Roman domination and forbidden subgraph, Bull. Inst. Combin. Appl. 39 (2003), 87-100.
[7] Cockayne, E.J., Grobler, P.J.P., Grundlingh, W.R., Munganga, J., and van Vuuren, J.H., Protection of a graph, Util. Math. 67 (2005), 19-32.
[8] Haynes, T.W., Hedetniemi, S.T., and Slater, P.J., "Fundamentals of Domination in Graphs", Marcel Dekker, Inc. New York, 1998.
[9] Henning, M.A., and Hedetniemi, S.M., Defending the Roman empire-A new stategy, Discrete Math. 266 (2003), 239-251.
[10] Mynhardt, C.M., Swart, H.C., and Ungerer, E., Excellent trees and secure domination, Util. Math. 67 (2005), 255-267.
[11] Weichsel, P.M., Dominating sets in n-cubes, J. Graph Theory 18(5) (1994), 479-488.

Files

Share

How to cite

Statistics