Secure domination and secure total domination in graphs
William F. Klostermeyer ; Christina M. Mynhardt
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 267-284 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270689 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1405,
     author = {William F. Klostermeyer and Christina M. Mynhardt},
     title = {Secure domination and secure total domination in graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {267-284},
     zbl = {1156.05043},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1405}
}

William F. Klostermeyer; Christina M. Mynhardt. Secure domination and secure total domination in graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 267-284. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1405/

[000] [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. | Zbl 1142.05045

[001] [2] S. Benecke, Higher Order Domination of Graphs (Master's Thesis, University of Stellenbosch, 2004).

[002] [3] S. Benecke, E.J. Cockayne and C.M. Mynhardt, Secure total domination in graphs, Utilitas Math. 74 (2007) 247-259. | Zbl 1183.05055

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

[004] [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. | Zbl 1052.05053

[005] [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. | Zbl 1052.05054

[006] [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. | Zbl 1233.05143

[007] [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. | Zbl 1036.05034

[008] [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. | Zbl 1051.05065

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

[010] [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. | Zbl 1081.05083

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

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

[013] [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. | Zbl 1169.05035

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

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

[016] [17] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 225-234, doi: 10.7151/dmgt.1178.

[017] [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. | Zbl 1022.05055

[018] [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. | Zbl 1024.05068

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

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

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

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