REVIEW 1 cited by
(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
In the eternal vertex cover problem, mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on its edges by moving to neighbor vertices. The eternal vertex cover problem consists in determining the minimum number of necessary guards. Motivated by previous literature, in this paper, we study the vertex cover and eternal vertex cover problems on regular grids, when passing from infinite to finite version of the same graphs, and we provide either coinciding or very tight lower and upper bounds on the number of necessary guards. To this aim, we generalize the notions of minimum vertex covers and minimum eternal vertex cover in order to be well defined for infinite grids.
Forward citations
Cited by 1 Pith paper
-
m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
The m-eternal domination problem and its Roman and Italian variants are NP-hard on narrow graph classes, and four infinite regular grids admit strongly optimal eternally-dominating guard sets.
Discussion (0). Continue with ORCID to comment.