Total Secure Domination in Graphs

Divya Rashmi S V; Shwetha H T; Shilpakala K

doi:10.5269/bspm.78188

Divya Rashmi S V Vidyavardhaka College of Engineering, Mysore
Shwetha H T Vidyavardhaka College of Engineering, Mysuru, Karnataka, India
Shilpakala K Srinivas Institute of Technology, Mangalore, Karnataka, India

Abstract

In this paper, we introduce and study the concept of total secure domination in
graphs. A set D ⊆ V(G) is called a total secure dominating set of a graph G
if it is a total dominating set (i.e., every vertex of G is adjacent to some vertex
in D) and for every vertex u / ∈ D, there exists a vertex v ∈ D adjacent to
u such that the set (D \{v}) ∪ {u} remains a dominating set in G (it need
not be total dominating). We denote the minimum size of such a set by γ_(ts)(G),
the total secure domination number. We establish fundamental properties, derive
bounds, and characterize γ_(ts)(G) for standard graph classes. We also propose
a greedy algorithm for trees. Finally, we discuss applications and directions for
future research

Downloads

Download data is not yet available.

References

[1] Cockayne, E.J., Dawes, R.M., Hedetniemi, S.M., Total domination in graphs,
Networks 10 (1980), no. 3, 211–219.
[2] Haynes, T.W., Hedetniemi, S.M., Slater, P.J., Fundamentals of Domination in
Graphs, Marcel Dekker, New York (1998).
[3] Breˇsar, B., Henning, M.A., Rall, D.F.,Secure domination in graphs, Discrete Appl.
Math. 156 (2008) no.7, 1176–1184.
[4] Klostermeyer, W.F., Mynhardt, C.M., Secure domination and secure total dom
ination in graphs, Discuss. Math. Graph Theory 28 (2008), 267–284.
[5] Henning, M.A., Yeo, A., Total Domination in Graphs, Springer (2013).
9
[6] Haynes, T.W., Hedetniemi, S.M., Slater, P.J., Recent advances on domination in
graphs: a survey, Discrete Math. 341(2018), no. 7, 2048–2065.
[7] Chang, X., Wang, Y.,Secure total domination in graphs: A new approach, J.
Comb. Optim. 38 (2019), no. 3, 835–852.
[8] Burger, A.P., Henning, M.A., van Vuuren, J.H., Vertex covers and secure
domination in graphs, Quaest. Math. 31 (2008), no. 3, 163–171.
[9] Chartrand, G., Lesniak, L., Graphs and Digraphs, Chapman & Hall/CRC (2005).
[10] Cockayne, E.J., Irredundance, secure domination and maximum degree in trees,
Discrete Math. 307 (2007), 12–17.
[11] Cockayne, E.J., Grobler, P.J.P., Gr¨ undlingh, W.R., Munganga, J., van Vuuren,
J.H., Protection of a graph, Util. Math. 67 (2005), 19–32.
[12] Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Domination in Graphs: Advanced
Topics, Marcel Dekker, New York (1998).
[13] Mynhardt, C.M., Swart, H.C., Ungerer, E., Excellent trees and secure domination,
Util. Math. 67 (2005), 255–267.
[14] Duginov, O., Secure total domination in graphs: Bounds and complexity, Discrete
Appl. Math. 222 (2017), 97–108.
[15] Benecke, S., Cockayne, E.J., Mynhardt, C.M.: Secure total domination in graphs.
Util. Math. 74 (2007).
[16] Cabrera Martinez, A., Montejano, L.P., Rodriguez-Velazquez, J.A.: On total
secure domination number of graphs. Symmetry 11 (2019), no. 9.
[17] Menon, M.K., Chithra, M.R., Secure domination of graph operators, Indian J.
Pure Appl. Math. 54 (2023), 1170–1176.
[18] Pradhan, D., Jha, A., On computing a minimum secure dominating set in block
graphs, Optim. 35(2018), no.2, 613–631.
[19] Wang, H., Zhao, Y., Deng, Y., The complexity of secure domination problems in
graphs, Discuss. Math. Graph Theory 38(2018), no. 2, 385–396.
[20] Henning, M.A.: A survey of selected recent results in total domination in graphs.
Discrete Math. 309 (2009), no. 1, 32–63.