Geodesic
Domination, Eternal Domination, and Clique Covering
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 283-300 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: dominating set, eternal dominating set, independent set, clique cover 
@article{DMGT_2015_35_2_a7,
     author = {Klostermeyer, William F. and Mynhardt, C.M.},
     title = {Domination, {Eternal} {Domination,} and {Clique} {Covering}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {283--300},
     year = {2015},
     volume = {35},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a7/}
}
TY  - JOUR
AU  - Klostermeyer, William F.
AU  - Mynhardt, C.M.
TI  - Domination, Eternal Domination, and Clique Covering
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 283
EP  - 300
VL  - 35
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a7/
LA  - en
ID  - DMGT_2015_35_2_a7
ER  - 
%0 Journal Article
%A Klostermeyer, William F.
%A Mynhardt, C.M.
%T Domination, Eternal Domination, and Clique Covering
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 283-300
%V 35
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a7/
%G en
%F DMGT_2015_35_2_a7
Klostermeyer, William F.; Mynhardt, C.M. Domination, Eternal Domination, and Clique Covering. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 283-300. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a7/

[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] 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

[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.

[5] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005) 169-180.

[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

[7] J. Goldwasser, W.F. Klostermeyer and C.M. Mynhardt, Eternal protection in grid graphs, Util. Math. 91 (2013) 47-64.

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[9] W. Klostermeyer and G. MacGillivray, Eternally secure sets, independence sets, and cliques, AKCE Int. J. Graphs Comb. 2 (2005) 119-122.

[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.

[11] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97-111.

[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

[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.

[15] F. Regan, Dynamic Variants of Domination and Independence in Graphs, Graduate Thesis, Rheinischen Friedrich-Wilhlems University, Bonn (2007).