Geodesic
Secure domination and secure total domination in graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 267-284.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: secure domination, total domination, secure total domination, clique covering 
@article{DMGT_2008_28_2_a4,
     author = {Klostermeyer, William and Mynhardt, Christina},
     title = {Secure domination and secure total domination in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {267--284},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a4/}
}
TY  - JOUR
AU  - Klostermeyer, William
AU  - Mynhardt, Christina
TI  - Secure domination and secure total domination in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 267
EP  - 284
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a4/
LA  - en
ID  - DMGT_2008_28_2_a4
ER  - 
%0 Journal Article
%A Klostermeyer, William
%A Mynhardt, Christina
%T Secure domination and secure total domination in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 267-284
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a4/
%G en
%F DMGT_2008_28_2_a4
Klostermeyer, William; Mynhardt, Christina. Secure domination and secure total domination in graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 267-284. http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a4/

[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.

[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.

[4] S. Benecke, P.J.P. Grobler and J.H. van Vuuren, Protection of complete multipartite graphs, Utilitas Math. 71 (2006) 161-168.

[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.

[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.

[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.

[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.

[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.

[10] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Total domination in $K_r$-covered graphs, Ars Combin. 71 (2004) 289-303.

[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.

[12] O. Favaron, H. Karami and S.M. Sheikholeslami, Total domination in K₅- and K₆-covered graphs, submitted.

[13] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180.

[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.

[15] P.J.P. Grobler and C.M. Mynhardt, Secure domination critical graphs, Discrete Math., to appear.

[16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[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.

[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.

[20] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007) 97-101.

[21] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. (2007), to appear.

[22] C.M. Mynhardt, H.C. Swart and E. Ungerer, Excellent trees and secure domination, Utilitas Math. 67 (2005) 255-267.

[23] I. Stewart, Defend the Roman Empire! Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136.