Perpetually Dominating Large Grids

Lamprou, I ORCID: 0000-0001-5337-7336, Martin, RA ORCID: 0000-0002-7043-503X and Schewe, S ORCID: 0000-0002-9093-9518 (2017) Perpetually Dominating Large Grids. In: 10th International Conference on Algorithms and Complexity, 2017-5-24 - 2017-5-26, Athens, Greece.

Text eternal-grids-Elements-version.pdf - Author Accepted Manuscript Download (416kB)

Abstract

In the Eternal Domination game, a team of guard tokens initially occupies a dominating set on a graph G. A rioter then picks a node without a guard on it and attacks it. The guards defend against the attack: one of them has to move to the attacked node, while each remaining one can choose to move to one of his neighboring nodes. The new guards' placement must again be dominating. This attack-defend procedure continues perpetually. The guards win if they can eternally maintain a dominating set against any sequence of attacks, otherwise the rioter wins. We study rectangular grids and provide the first known general upper bound for these graphs. Our novel strategy implements a square rotation principle and eternally dominates m x n grids by using approximately (mn)/5 guards, which is asymptotically optimal even for ordinary domination.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Eternal domination, Combinatorial game, Two players, Graph Protection, Grid
Depositing User:	Symplectic Admin
Date Deposited:	20 Feb 2017 12:52
Last Modified:	15 Mar 2024 09:05
DOI:	10.1007/978-3-319-57586-5_33
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005868