Geodesic
Eternal Domination: Criticality and Reachability
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 63-77 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

We show that for every minimum eternal dominating set, D, of a graph G and every vertex v ∈ D, there is a sequence of attacks at the vertices of G which can be defended in such a way that an eternal dominating set not containing v is reached. The study of the stronger assertion that such a set can be reached after a single attack is defended leads to the study of graphs which are critical in the sense that deleting any vertex reduces the eternal domination number. Examples of these graphs and tight bounds on connectivity, edge-connectivity and diameter are given. It is also shown that there exist graphs in which deletion of any edge increases the eternal domination number, and graphs in which addition of any edge decreases the eternal domination number.
Keywords: dominating set, eternal dominating set, critical graphs 
@article{DMGT_2017_37_1_a5,
     author = {Klostermeyer, William F. and MacGillivray, Gary},
     title = {Eternal {Domination:} {Criticality} and {Reachability}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {63--77},
     year = {2017},
     volume = {37},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a5/}
}
TY  - JOUR
AU  - Klostermeyer, William F.
AU  - MacGillivray, Gary
TI  - Eternal Domination: Criticality and Reachability
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 63
EP  - 77
VL  - 37
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a5/
LA  - en
ID  - DMGT_2017_37_1_a5
ER  - 
%0 Journal Article
%A Klostermeyer, William F.
%A MacGillivray, Gary
%T Eternal Domination: Criticality and Reachability
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 63-77
%V 37
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a5/
%G en
%F DMGT_2017_37_1_a5
Klostermeyer, William F.; MacGillivray, Gary. Eternal Domination: Criticality and Reachability. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 63-77. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a5/

[1] R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173–179. doi:10.1002/net.3230180304

[2] A.P. Burger, E.J. Cockayne, W.R. Gründlingh, C.M. Mynhardt, J.H. van Vuuren and W. Winterbach, Infinite order domination in graph, J. Combin. Math. Combin. Comput. 50 (2004) 179–194.

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

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

[5] G. Fricke, S.M. Hedetniemi, S.T. Hedetniemi and K.R. Hutson, γ-graphs of graphs, Discuss. Math. Graph Theory 31 (2011) 517–531. doi:10.7151/dmgt.1562

[6] J. Fulman, D. Hanson and G. MacGillivray, Vertex domination-critical graphs, Networks 25 (1995) 41–43.

[7] R. Haas and K. Seyffarth, The k-dominating graph, Graphs Combin. 30 (2014) 609–617. doi:10.1007/s00373-013-1302-3

[8] W. Klostermeyer, M. Lawrence and G. MacGillivray, Dynamic dominating sets: the eviction model for eternal domination, J. Combin. Math. Combin. Comput. (2016), to appear.

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

[10] W. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. (2016), to appear.