Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs
DOI:
https://doi.org/10.7155/jgaa.v28i3.2972Keywords:
Eternal vertex cover, Chain graphs, Split graphs, CographsAbstract
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 eternal vertex cover number 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.
Downloads
Downloads
Published
How to Cite
Issue
Section
Categories
License
Copyright (c) 2024 Kaustav Paul, Arti Pandey
This work is licensed under a Creative Commons Attribution 4.0 International License.