Structural Parameterizations for Eternal Vertex Cover
Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$. To begin with, the defender places $k$ guards on vertices of $G$. The attacker, on their turn, can choose an edge $e$ not already occupied at both endpoints to "attack". The edge $e$ is defended if a guard moves along the edge $e$. The defender, on their turn, can move any subset of guards. A guard can only move to a neighboring vertex. The minimum number of guards needed to indefinitely defend against any sequence of attacks is called the eternal vertex cover number, generalizing the classic vertex…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.17891
curl -X POST /api/v1/records/arxiv/2609.17891/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.17891/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'