Agradecimentos: The authors would like to thank Professor Célia P. de Mello for suggesting the investigation of the EDSP for proper interval graphs, and the anonymous reviewers for their careful reading of the paper and valuable comments. This work was funded by grants 477692/2012-5, 141964/2013-8, 302804/2010-2, and 303947/2008-0 from Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, Brazil) Ver menos

Abstract: 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 Ver menos