# 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

## Access Full Article

top## Abstract

top## How to cite

topWilliam 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] 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] 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] 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] 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] 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] 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] J. Goldwasser, W.F. Klostermeyer and C.M. Mynhardt, Eternal protection in grid graphs, Util. Math. 91 (2013) 47-64. Zbl1300.05177
- [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [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] 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] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97-111. Zbl1176.05057
- [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] W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Movement on Networks, Cambridge University Press (2014).
- [14] G. Ravindra, Well covered graphs, J. Comb. Inf. Syst. Sci. 2 (1977) 20-21. Zbl0396.05007
- [15] F. Regan, Dynamic Variants of Domination and Independence in Graphs, Graduate Thesis, Rheinischen Friedrich-Wilhlems University, Bonn (2007).

## NotesEmbed ?

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