Header menu link for other important links
X
On graphs with minimal eternal vertex cover number
, L.S. Chandran, M. Francis, V. Prabhakaran, J.N. Warrier,
Published in Springer Verlag
2019
Volume: 11394 LNCS
   
Pages: 263 - 273
Abstract
The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of an attacker-defender game. The minimum number of guards required to protect a graph from an infinite sequence of attacks is the eternal vertex cover number (evc) of the graph. It is known that, given a graph G and an integer k, checking whether (G)≤k is NP-Hard. However, for any graph G, (Formula presentd), where mvc(G) is the minimum vertex cover number of G. Precise value of eternal vertex cover number is known only for certain very basic graph classes like trees, cycles and grids. Though a characterization is known for graphs for which evc(G) = 2 mvc(G), a characterization of graphs for which evc(G) = mvc(G) remained open. Here, we achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For some graph classes including biconnected chordal graphs, our characterization leads to a polynomial time algorithm to precisely determine evc(G) and to determine a safe strategy of guard movement in each round of the game with evc(G) guards. © Springer Nature Switzerland AG 2019.