Some algorithmic results for eternal vertex cover problem in graphs (Q6636999)

The eternal vertex cover number is a graph parameter that is related to the minimum vertex cover number. It is the minimum number of guards on the vertices that are needed to defend a graph against attacks on the edges. The guards on the vertices have to form a vertex cover. Some attackers can choose one edge then the guards can move along the edges of the graph such that at least one guard moves along the attacked edge and the guards form still a vertex cover afterward. This problem was introduced in [\textit{W. F. Klostermeyer} and \textit{C. M. Mynhardt}, Australas. J. Comb. 45, 235--250 (2009; Zbl 1207.05141)], where it is also shown that the eternal vertex cover number is at most twice the minimum vertex cover number.\N\NIt is \(\mathcal{NP}\)-hard to compute the eternal vertex cover number of a graph, even for bipartite graphs. There are polynomial time algorithms for special graph classes, for example, chordal graphs. In this article, new polynomial time algorithms for some other graph classes are developed. Namely for chain graphs, split graphs, and \(P_4\)-sparse graphs.\N\NA preliminary version of the article appeared in [the authors, Lect. Notes Comput. Sci. 13973, 242--253 (2023; Zbl 07770296)].