Discussiones Mathematicae Graph Theory 28(2) (2008) 267-284
doi: 10.7151/dmgt.1405

[BIBTex] [PDF] [PS]


William F. Klostermeyer

School of Computing
University of North Florida
Jacksonville, FL 32224-2669
e-mail: wkloster@unf.edu

Christina M. Mynhardt

Department of Mathematics and Statistics
University of Victoria, P.O. Box 3060 STN CSC
Victoria, BC, Canada V8W 3R4
e-mail: mynhardt@math.uvic.ca


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.

2000 Mathematics Subject Classification: 05C69.


[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 Kr-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 K5- and K6-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.

Received 29 June 2007
Revised 25 April 2008
Accepted 25 April 2008