Skip to Main content Skip to Navigation
Reports

Eternal Domination in Strong Grids

Fionn Mc Inerney 1 Nicolas Nisse 1 Stéphane Pérennes 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In the eternal domination game played on graphs, 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 on their turn. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper continues the study of the eternal domination game on strong grids $P n P m$. Cartesian grids have been vastly studied with tight bounds existing for small grids such as $k × n$ grids for $k ∈ {2, 3, 4, 5}$. It was recently proven that the eternal domination number of these grids in general is within an additive factor of $O(n + m)$ 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 $nm 6 + O(n + m)$. There exists a gap still between the lower and upper bound as the domination number (current lower bound) of the strong grid is nm 9. We prove that, for all n, $m ∈ N *$ such that $m ≥ n$, $nm 9 + Ω(n + m) = γ ∞ all (P n P m) = nm 9 + O(m √ n)$.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01790322
Contributor : Fionn Mc Inerney Connect in order to contact the contributor
Submitted on : Friday, May 11, 2018 - 9:42:33 PM
Last modification on : Tuesday, December 7, 2021 - 4:10:49 PM
Long-term archiving on: : Tuesday, September 25, 2018 - 12:06:41 AM

File

eterdom_grids_new_v02.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01790322, version 1

Citation

Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes. Eternal Domination in Strong Grids. [Research Report] Inria & Université Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France. 2018. ⟨hal-01790322v1⟩

Share

Metrics

Les métriques sont temporairement indisponibles