A note on the eternal dominating set problem

Stephen Finbow (), Serge Gaspers (), Margaret-Ellen Messinger () and Paul Ottaway ()
Additional contact information
Stephen Finbow: St. Francis Xavier University
Serge Gaspers: UNSW Sydney and Data61, CSIRO
Margaret-Ellen Messinger: Mount Allison University
Paul Ottaway: Capilano University

International Journal of Game Theory, 2018, vol. 47, issue 2, No 8, 543-555

Abstract: Abstract We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [Goddard et al. (J. Combin. Math. Combin. Comput. 52:169–180, 2005)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.

Keywords: Graph protection; Graph domination; Eternal domination; Combinatorial game theory; 05C69; 05C57; 68R15; 91A46 (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-018-0623-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:47:y:2018:i:2:d:10.1007_s00182-018-0623-0

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-018-0623-0

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().