The Eternal Dominating Set problem for proper interval graphs

In this paper, we solve the Eternal Dominating Set problem for proper interval graphs. We prove that, in this case, the optimal value of the problem equals the largest size of an independent set. As a consequence, we show that the problem can be solved in linear time for such graphs. To obtain the result, we first consider another problem in which a vertex can be occupied by an arbitrary number of guards. We then derive a lower bound on the optimal value of this latter problem, and prove that, for proper interval graphs, it is the same as the optimum of the first problem.