@article{Paul_Pandey_2024, title={Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs}, volume={28}, url={https://jgaa.info/index.php/jgaa/article/view/2972}, DOI={10.7155/jgaa.v28i3.2972}, abstractNote={<p>The eternal vertex cover problem is a variant of the vertex cover problem. It is a two-player (attacker and defender) game in which, given a graph $G=(V,E)$, the defender needs to allocate guards at some vertices so that the allocated vertices form a vertex cover. The attacker can attack one edge at a time, and the defender needs to move the guards along the edges such that at least one guard moves through the attacked edge and the new configuration still remains a vertex cover. The attacker wins if no such move exists for the defender. The defender wins if there exists a strategy to defend the graph against infinite sequence of attacks. The minimum number of guards with which the defender can form a winning strategy is called the <em>eternal vertex cover number</em> of $G$, and is denoted by $evc(G)$. Given a graph $G$, the problem of finding the eternal vertex cover number is NP-hard for general graphs and remains NP-hard even for bipartite graphs. We have given a polynomial time algorithm to find the Eternal vertex cover number in chain graphs and $P_4$-sparse graphs. We have also given a linear-time algorithm to find the eternal vertex cover number for split graphs, an important subclass of chordal graphs.</p>}, number={3}, journal={Journal of Graph Algorithms and Applications}, author={Paul, Kaustav and Pandey, Arti}, year={2024}, month={Sep.}, pages={69–85} }