TY - JOUR
AU - Paul, Kaustav
AU - Pandey, Arti
PY - 2024/09/10
Y2 - 2024/10/08
TI - Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 3
SE -
DO - 10.7155/jgaa.v28i3.2972
UR - https://jgaa.info/index.php/jgaa/article/view/2972
SP - 69-85
AB - <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>
ER -