Domination, Eternal Domination, and Clique Covering

William F. Klostermeyer; C.M. Mynhardt

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 283-300
  • ISSN: 2083-5892

Abstract

top
Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.

How to cite

top

William F. Klostermeyer, and C.M. Mynhardt. "Domination, Eternal Domination, and Clique Covering." Discussiones Mathematicae Graph Theory 35.2 (2015): 283-300. <http://eudml.org/doc/271100>.

@article{WilliamF2015,
abstract = {Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.},
author = {William F. Klostermeyer, C.M. Mynhardt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; eternal dominating set; independent set; clique cover},
language = {eng},
number = {2},
pages = {283-300},
title = {Domination, Eternal Domination, and Clique Covering},
url = {http://eudml.org/doc/271100},
volume = {35},
year = {2015},
}

TY - JOUR
AU - William F. Klostermeyer
AU - C.M. Mynhardt
TI - Domination, Eternal Domination, and Clique Covering
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 283
EP - 300
AB - Eternal and m-eternal domination are concerned with using mobile guards to protect a graph against infinite sequences of attacks at vertices. Eternal domination allows one guard to move per attack, whereas more than one guard may move per attack in the m-eternal domination model. Inequality chains consisting of the domination, eternal domination, m-eternal domination, independence, and clique covering numbers of graph are explored in this paper. Among other results, we characterize bipartite and triangle-free graphs with domination and eternal domination numbers equal to two, trees with equal m-eternal domination and clique covering numbers, and two classes of graphs with equal domination, eternal domination and clique covering numbers.
LA - eng
KW - dominating set; eternal dominating set; independent set; clique cover
UR - http://eudml.org/doc/271100
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] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241-249. doi:10.1002/jgt.3190030306[Crossref] Zbl0418.05049
  3. [3] A. Braga, C.C. de Souza and O. Lee, A note on the paper “Eternal security in graphs” by Goddard, Hedetniemi, and Hedetniemi (2005), J. Combin. Math. Combin. Comput., to appear. 
  4. [4] A.P. Burger, E.J. Cockayne, W.R. Gr¨undlingh, 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
  5. [5] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180. Zbl1067.05051
  6. [6] 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[Crossref][WoS] Zbl1169.05035
  7. [7] J. Goldwasser, W.F. Klostermeyer and C.M. Mynhardt, Eternal protection in grid graphs, Util. Math. 91 (2013) 47-64. Zbl1300.05177
  8. [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  9. [9] W. Klostermeyer and G. MacGillivray, Eternally secure sets, independence sets, and cliques, AKCE Int. J. Graphs Comb. 2 (2005) 119-122. Zbl1102.05043
  10. [10] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed inde- pendence number , J. Combin. Math. Combin. Comput. 63 (2007) 97-101. Zbl1138.05053
  11. [11] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97-111. Zbl1176.05057
  12. [12] W.F. Klostermeyer and C.M. Mynhardt, Vertex covers and eternal dominating sets, Discrete Appl. Math. 160 (2012) 1183-1190. doi:10.1016/j.dam.2011.11.034[WoS][Crossref] Zbl06039486
  13. [13] W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Movement on Networks, Cambridge University Press (2014). 
  14. [14] G. Ravindra, Well covered graphs, J. Comb. Inf. Syst. Sci. 2 (1977) 20-21. Zbl0396.05007
  15. [15] F. Regan, Dynamic Variants of Domination and Independence in Graphs, Graduate Thesis, Rheinischen Friedrich-Wilhlems University, Bonn (2007). 

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.