ArticleOriginal scientific text

Title

Secure domination and secure total domination in graphs

Authors 1, 2

Affiliations

  1. School of Computing, University of North Florida, Jacksonville, FL 32224-2669
  2. Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, BC, Canada V8W 3R4

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

Bibliography

  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 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.
Pages:
267-284
Main language of publication
English
Received
2007-06-29
Accepted
2008-04-25
Published
2008
Exact and natural sciences