English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The eternal vertex cover problem is a variant of the classical vertex coverproblem where a set of guards on the vertices have to be dynamicallyreconfigured from one vertex cover to another in every round of anattacker-defender game. The minimum number of guards required to protect agraph $G$ from an infinite sequence of attacks is the eternal vertex covernumber of $G$, denoted by $evc(G)$. It is known that, given a graph $G$ and aninteger $k$, checking whether $evc(G) \le k$ is NP-hard. However, it is unknownwhether this problem is in NP or not. Precise value of eternal vertex covernumber is known only for certain very basic graph classes like trees, cyclesand grids.  For any graph $G$, it is known that $mvc(G) \le evc(G) \le 2 mvc(G)$, where$mvc(G)$ is the minimum vertex cover number of $G$. Though a characterizationis known for graphs for which $evc(G) = 2 mvc(G)$, a characterization of graphsfor which $evc(G) = mvc(G)$ remained open. Here, we achieve such acharacterization for a class of graphs that includes chordal graphs andinternally triangulated planar graphs. For some graph classes includingbiconnected chordal graphs, our characterization leads to a polynomial timealgorithm to precisely determine $evc(G)$ and to determine a safe strategy ofguard movement in each round of the game with $evc(G)$ guards.  The characterization also leads to NP-completeness results for the eternalvertex cover problem for some graph classes including biconnected internallytriangulated planar graphs. To the best of our knowledge, these are the firstNP-completeness results known for the problem for any graph class.

On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide