Eternally dominating large grids

Lamprou, Ioannis ORCID: 0000-0001-5337-7336, Martin, Russell ORCID: 0000-0002-7043-503X and Schewe, Sven ORCID: 0000-0002-9093-9518 (2019) Eternally dominating large grids. Theoretical Computer Science, 794. pp. 27-46.

Text elements-eternal-final.pdf - Author Accepted Manuscript Download (660kB)

Abstract

© 2018 Elsevier B.V. In the m-Eternal Domination game, a team of guard tokens initially occupies a dominating set on a graph G. An attacker then picks a vertex without a guard on it and attacks it. The guards defend against the attack: one of them has to move to the attacked vertex, while each remaining one can choose to move to one of his neighboring vertices. The new guards’ placement must again be dominating. This attack-defend procedure continues eternally. The guards win if they can eternally maintain a dominating set against any sequence of attacks, otherwise the attacker wins. The m-eternal domination number for a graph G is the minimum amount of guards such that they win against any attacker strategy in G (all guards move model). We study rectangular grids and provide the first known general upper bound on the m-eternal domination number for these graphs. Our novel strategy implements a square rotation principle and eternally dominates m×n grids by using approximately [Formula presented] guards, which is asymptotically optimal even for ordinary domination.

Item Type:	Article
Uncontrolled Keywords:	Eternal domination, Combinatorial game, Two players, Graph Protection, Grid
Depositing User:	Symplectic Admin
Date Deposited:	15 Oct 2018 09:29
Last Modified:	19 Jan 2023 01:14
DOI:	10.1016/j.tcs.2018.09.008
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3027567