Eternal Domination: Criticality and Reachability

William F. Klostermeyer, and Gary MacGillivray. "Eternal Domination: Criticality and Reachability." Discussiones Mathematicae Graph Theory 37.1 (2017): 63-77. <http://eudml.org/doc/288042>.

@article{WilliamF2017,
abstract = {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.},
author = {William F. Klostermeyer, Gary MacGillivray},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; eternal dominating set; critical graphs},
language = {eng},
number = {1},
pages = {63-77},
title = {Eternal Domination: Criticality and Reachability},
url = {http://eudml.org/doc/288042},
volume = {37},
year = {2017},
}

TY - JOUR
AU - William F. Klostermeyer
AU - Gary MacGillivray
TI - Eternal Domination: Criticality and Reachability
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 63
EP - 77
AB - 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.
LA - eng
KW - dominating set; eternal dominating set; critical graphs
UR - http://eudml.org/doc/288042
ER -