PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 1 | 63-77
Tytuł artykułu

Eternal Domination: Criticality and Reachability

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
37
Numer
1
Strony
63-77
Opis fizyczny
Daty
wydano
2017-02-01
otrzymano
2015-08-10
poprawiono
2016-02-16
zaakceptowano
2016-02-16
online
2017-01-13
Twórcy
  • School of Computing, University of North Florida, Jacksonville, FL 32224, wkloster@unf.edu
  • Department of Mathematics and Statistics, University of Victoria, P.O. Box 3060 STN CSC, Victoria, BC, V8W 3R4, gmacgill@math.uvic.ca
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1918
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.