Perpetually dominating large grids

DOI10.1007/978-3-319-57586-5_33MaRDI QIDQ6828306zbMATH OpenFDO

Authors Ioannis Lamprou, Russell Martin, Sven Schewe

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_33

zbMATH Keywords

combinatorial gameeternal dominationgraph protectiongridtwo players

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 2-person games (91A05) Games involving graphs (91A43)

Review text

In this paper, the authors consider the following game on a graph, called 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.\N\NThe authors show that approximately \(\frac {mn} 5\) guards win the game on \(m\times n\) grids.\N\NFor the entire collection see [Zbl 1361.68008].

This page was built for publication: Perpetually dominating large grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828306)