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.
@article{bwmeta1.element.doi-10_7151_dmgt_1799,
author = {William F. Klostermeyer and C.M. Mynhardt},
title = {Domination, Eternal Domination, and Clique Covering},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {283-300},
zbl = {1311.05151},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1799}
}
William F. Klostermeyer; C.M. Mynhardt. Domination, Eternal Domination, and Clique Covering. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 283-300. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1799/
[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. | Zbl 1142.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] | Zbl 0418.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. | Zbl 1052.05054
[5] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180. | Zbl 1067.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] | Zbl 1169.05035
[7] J. Goldwasser, W.F. Klostermeyer and C.M. Mynhardt, Eternal protection in grid graphs, Util. Math. 91 (2013) 47-64. | Zbl 1300.05177
[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[9] W. Klostermeyer and G. MacGillivray, Eternally secure sets, independence sets, and cliques, AKCE Int. J. Graphs Comb. 2 (2005) 119-122. | Zbl 1102.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. | Zbl 1138.05053
[11] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97-111. | Zbl 1176.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] | Zbl 06039486
[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. | Zbl 0396.05007
[15] F. Regan, Dynamic Variants of Domination and Independence in Graphs, Graduate Thesis, Rheinischen Friedrich-Wilhlems University, Bonn (2007).