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 neighboring vertices. The eternal vertex cover problem consists of determining the minimum number of necessary guards. Motivated by previous literature, we study the vertex cover and eternal vertex cover problems on regular grids when passing from infinite to finite versions 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.

(Eternal) vertex cover numbers of infinite and finite grid graphs / Calamoneri, Tiziana; Corò, Federico. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 1042:(2025). [10.1016/j.tcs.2025.115261]

(Eternal) vertex cover numbers of infinite and finite grid graphs

Calamoneri, Tiziana;Corò, Federico
2025

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 neighboring vertices. The eternal vertex cover problem consists of determining the minimum number of necessary guards. Motivated by previous literature, we study the vertex cover and eternal vertex cover problems on regular grids when passing from infinite to finite versions 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.
2025
eternal vertex cover; infinite grids; finite grids
01 Pubblicazione su rivista::01a Articolo in rivista
(Eternal) vertex cover numbers of infinite and finite grid graphs / Calamoneri, Tiziana; Corò, Federico. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 1042:(2025). [10.1016/j.tcs.2025.115261]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1763032
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact