# Secure domination and secure total domination in graphs

William F. Klostermeyer; Christina M. Mynhardt

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 2, page 267-284
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topWilliam F. Klostermeyer, and Christina M. Mynhardt. "Secure domination and secure total domination in graphs." Discussiones Mathematicae Graph Theory 28.2 (2008): 267-284. <http://eudml.org/doc/270689>.

@article{WilliamF2008,

abstract = {A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X-\{x\}) ∪ \{u\}$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_s(G)(γ_\{st\}(G))$. We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_\{st\}(G) ≤ γ_s(G)$. We also show that $γ_\{st\}(G)$ is at most twice the clique covering number of G, and less than three times the independence number. With the exception of the independence number bound, these bounds are sharp.},

author = {William F. Klostermeyer, Christina M. Mynhardt},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {secure domination; total domination; secure total domination; clique covering},

language = {eng},

number = {2},

pages = {267-284},

title = {Secure domination and secure total domination in graphs},

url = {http://eudml.org/doc/270689},

volume = {28},

year = {2008},

}

TY - JOUR

AU - William F. Klostermeyer

AU - Christina M. Mynhardt

TI - Secure domination and secure total domination in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 2

SP - 267

EP - 284

AB - A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X-{x}) ∪ {u}$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_s(G)(γ_{st}(G))$. We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{st}(G) ≤ γ_s(G)$. We also show that $γ_{st}(G)$ is at most twice the clique covering number of G, and less than three times the independence number. With the exception of the independence number bound, these bounds are sharp.

LA - eng

KW - secure domination; total domination; secure total domination; clique covering

UR - http://eudml.org/doc/270689

ER -

## References

top- [1] M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray and J. Yellen, Maximum demand graphs for eternal security, J. Combin. Math. Combin. Comput. 61 (2007) 111-128. Zbl1142.05045
- [2] S. Benecke, Higher Order Domination of Graphs (Master's Thesis, University of Stellenbosch, 2004).
- [3] S. Benecke, E.J. Cockayne and C.M. Mynhardt, Secure total domination in graphs, Utilitas Math. 74 (2007) 247-259. Zbl1183.05055
- [4] S. Benecke, P.J.P. Grobler and J.H. van Vuuren, Protection of complete multipartite graphs, Utilitas Math. 71 (2006) 161-168. Zbl1200.05152
- [5] A.P. Burger, E.J. Cockayne, W.R. Gründlingh, C.M. Mynhardt, J.H. van Vuuren and W. Winterbach, Finite order domination in graphs, J. Combin. Math. Combin. Comput. 49 (2004 159-175. Zbl1052.05053
- [6] A.P. Burger, E.J. Cockayne, W.R. Gründlingh, C.M. Mynhardt, J.H. van Vuuren and W. Winterbach, Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004) 179-194. Zbl1052.05054
- [7] E.J. Cockayne, Irredundance, secure domination and maximum degree in trees, Discrete Math. 307 (2007) 12-17, doi: 10.1016/j.disc.2006.05.037. Zbl1233.05143
- [8] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-12, doi: 10.1016/j.disc.2003.06.004. Zbl1036.05034
- [9] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl. 39 (2003) 87-100. Zbl1051.05065
- [10] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Total domination in ${K}_{r}$-covered graphs, Ars Combin. 71 (2004) 289-303. Zbl1078.05063
- [11] E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Utilitas Math. 67 (2005) 19-32. Zbl1081.05083
- [12] O. Favaron, H. Karami and S.M. Sheikholeslami, Total domination in K₅- and K₆-covered graphs, submitted. Zbl1153.05043
- [13] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180. Zbl1067.05051
- [14] J. Goldwasser and W.F. Klostermeyer, Tight bounds for eternal dominating sets in graphs, Discrete Math. 308 (2008) 2589-2593, doi: 10.1016/j.disc.2007.06.005. Zbl1169.05035
- [15] P.J.P. Grobler and C.M. Mynhardt, Secure domination critical graphs, Discrete Math., to appear. Zbl1189.05126
- [16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [17] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 225-234, doi: 10.7151/dmgt.1178.
- [18] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115, doi: 10.1016/S0012-365X(03)00040-2. Zbl1022.05055
- [19] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire - A new strategy, Discrete Math. 266 (2003) 239-251, doi: 10.1016/S0012-365X(02)00811-7. Zbl1024.05068
- [20] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007) 97-101. Zbl1138.05053
- [21] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. (2007), to appear. Zbl1176.05057
- [22] C.M. Mynhardt, H.C. Swart and E. Ungerer, Excellent trees and secure domination, Utilitas Math. 67 (2005) 255-267. Zbl1071.05058
- [23] I. Stewart, Defend the Roman Empire! Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.