论文标题
（永恒）无限和有限网格图的顶点覆盖码
(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs
论文作者
论文摘要
在永恒的顶点覆盖问题中，图表顶点上的移动警卫通过移动到邻居的顶点来防御其边缘上无限攻击序列。永恒的顶点覆盖问题包括确定必要的后卫的最小数量。在以前的文献中，在本文中，我们研究了正常网格的顶点覆盖物和永恒的顶点覆盖问题，当时从无限版本到同一图的有限版本时，我们提供了必要守卫数量的同时或非常紧的下层和上限。为此，我们概括了最小顶点覆盖的概念和最小的永恒顶点覆盖物，以便为无限网格定义。
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.
