×

On graphs with minimal eternal vertex cover number. (English) Zbl 1522.05361

Pal, Sudebkumar Prasant (ed.) et al., Algorithms and discrete applied mathematics. 5th international conference, CALDAM 2019, Kharagpur, India, February 14–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11394, 263-273 (2019).
Summary: 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 \({\text{evc}}(G) \le k\) is NP-Hard. However, for any graph \(G, {\text{mvc}}(G) \le{\text{evc}}(G) \le 2 {\text{mvc}}(G)\), where \({\text{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 \({\text{evc}}(G) = 2{\text{mvc}}(G)\), a characterization of graphs for which \({\text{evc}}(G) = {\text{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 \({\text{evc}}(G)\) and to determine a safe strategy of guard movement in each round of the game with \({\text{evc}}(G)\) guards.
For the entire collection see [Zbl 1410.68018].

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv