Eternal Security in Graphs

Abstract

Consider placing a guard on each vertex of a dominating set $S_0$ of a graph. If for every vertex $v\notin S_0$, there is a corresponding guard at an adjacent vertex $u$ for which the resulting set $S_1=S_0–\{u\}\cup \{v\}$ is dominating, then we say that $S_0$ is $1$-secure. It is eternally $1$-secure if for any sequence $v_1,v_2,\dots ,v_k$ of vertices, there exists a sequence of guards $u_1,u_2,\dots ,u_k$ with $u_i\in S_{i-1}$ and $u_i$ equal to or adjacent to $v_i$, such that each set $S_i=S_{i-1}–\{u_i\}\cup \{v_i\}$ is dominating. We investigate the minimum cardinality of an eternally secure set. In particular, we refute a conjecture of Burger et al. We also investigate eternal $m$-security, in which all guards can move simultaneously.