DMGT

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

SECURE DOMINATION AND SECURE TOTAL DOMINATION IN GRAPHS

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

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.

Keywords: secure domination, total domination, secure total domination, clique covering.

2000 Mathematics Subject Classification: 05C69.

References

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

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