Secure domination and secure total domination in graphs

William F. Klostermeyer; Christina M. Mynhardt

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 2, page 267-284
  • ISSN: 2083-5892

Abstract

top
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 ) ( γ s t ( G ) ) . We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then γ s t ( G ) ≤ γ s ( G ) . We also show that γ s t ( 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.

How to cite

top

William F. Klostermeyer, and Christina M. Mynhardt. "Secure domination and secure total domination in graphs." Discussiones Mathematicae Graph Theory 28.2 (2008): 267-284. <http://eudml.org/doc/270689>.

@article{WilliamF2008,
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.},
author = {William F. Klostermeyer, Christina M. Mynhardt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {secure domination; total domination; secure total domination; clique covering},
language = {eng},
number = {2},
pages = {267-284},
title = {Secure domination and secure total domination in graphs},
url = {http://eudml.org/doc/270689},
volume = {28},
year = {2008},
}

TY - JOUR
AU - William F. Klostermeyer
AU - Christina M. Mynhardt
TI - Secure domination and secure total domination in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 2
SP - 267
EP - 284
AB - 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.
LA - eng
KW - secure domination; total domination; secure total domination; clique covering
UR - http://eudml.org/doc/270689
ER -

References

top
  1. [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. Zbl1142.05045
  2. [2] S. Benecke, Higher Order Domination of Graphs (Master's Thesis, University of Stellenbosch, 2004). 
  3. [3] S. Benecke, E.J. Cockayne and C.M. Mynhardt, Secure total domination in graphs, Utilitas Math. 74 (2007) 247-259. Zbl1183.05055
  4. [4] S. Benecke, P.J.P. Grobler and J.H. van Vuuren, Protection of complete multipartite graphs, Utilitas Math. 71 (2006) 161-168. Zbl1200.05152
  5. [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. Zbl1052.05053
  6. [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. Zbl1052.05054
  7. [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. Zbl1233.05143
  8. [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. Zbl1036.05034
  9. [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. Zbl1051.05065
  10. [10] E.J. Cockayne, O. Favaron and C.M. Mynhardt, Total domination in K r -covered graphs, Ars Combin. 71 (2004) 289-303. Zbl1078.05063
  11. [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. Zbl1081.05083
  12. [12] O. Favaron, H. Karami and S.M. Sheikholeslami, Total domination in K₅- and K₆-covered graphs, submitted. Zbl1153.05043
  13. [13] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180. Zbl1067.05051
  14. [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. Zbl1169.05035
  15. [15] P.J.P. Grobler and C.M. Mynhardt, Secure domination critical graphs, Discrete Math., to appear. Zbl1189.05126
  16. [16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  17. [17] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 225-234, doi: 10.7151/dmgt.1178. 
  18. [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. Zbl1022.05055
  19. [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. Zbl1024.05068
  20. [20] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007) 97-101. Zbl1138.05053
  21. [21] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. (2007), to appear. Zbl1176.05057
  22. [22] C.M. Mynhardt, H.C. Swart and E. Ungerer, Excellent trees and secure domination, Utilitas Math. 67 (2005) 255-267. Zbl1071.05058
  23. [23] I. Stewart, Defend the Roman Empire! Scientific American, December 1999, 136-138, doi: 10.1038/scientificamerican1299-136. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.