Geodesic
A method for eternally dominating strong grids
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1.

Voir la notice de l'article provenant de la source Episciences

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m + n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn 6 + O(m + n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn 7 + O(m + n). While this does not improve upon a recently announced bound of ⎡m/3⎤ x⎡n/3⎤ + O(m √ n) [Mc Inerney, Nisse, Pérennes, HAL archives, 2018; Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179.
DOI : 10.23638/DMTCS-22-1-8
Classification : 05C57, 05C69, 91A43, 91A46 
@article{DMTCS_2020_22_1_a7,
     author = {Gagnon, Aliz\'ee and Hassler, Alexander and Huang, Jerry and Krim-Yee, Aaron and Mc Inerney, Fionn and Zacar{\'\i}as, Andr\'es and Seamone, Ben and Virgile, Virg\'elot},
     title = {A method for eternally dominating strong grids},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-8/}
}
TY  - JOUR
AU  - Gagnon, Alizée
AU  - Hassler, Alexander
AU  - Huang, Jerry
AU  - Krim-Yee, Aaron
AU  - Mc Inerney, Fionn
AU  - Zacarías, Andrés
AU  - Seamone, Ben
AU  - Virgile, Virgélot
TI  - A method for eternally dominating strong grids
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-8/
DO  - 10.23638/DMTCS-22-1-8
LA  - en
ID  - DMTCS_2020_22_1_a7
ER  - 
%0 Journal Article
%A Gagnon, Alizée
%A Hassler, Alexander
%A Huang, Jerry
%A Krim-Yee, Aaron
%A Mc Inerney, Fionn
%A Zacarías, Andrés
%A Seamone, Ben
%A Virgile, Virgélot
%T A method for eternally dominating strong grids
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-8/
%R 10.23638/DMTCS-22-1-8
%G en
%F DMTCS_2020_22_1_a7
Gagnon, Alizée; Hassler, Alexander; Huang, Jerry; Krim-Yee, Aaron; Mc Inerney, Fionn; Zacarías, Andrés; Seamone, Ben; Virgile, Virgélot. A method for eternally dominating strong grids. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi : 10.23638/DMTCS-22-1-8. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-8/

Cité par Sources :