Eternal Domination: Criticality and Reachability

• Autorzy: William F. Klostermeyer , Gary MacGillivray
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

dominating set; eternal dominating set; critical graphs

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 63-77

Daty

wydano

2017-02-01

otrzymano

2015-08-10

poprawiono

2016-02-16

zaakceptowano

2016-02-16

online

2017-01-13

Twórcy

autor

William F. Klostermeyer

• School of Computing, University of North Florida, Jacksonville, FL 32224

autor

Gary MacGillivray

• Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, BC, V8W 3R4

Identyfikatory

DOI

10.7151/dmgt.1918