Calamoneri, TizianaCor�, FedericoMisra, NeeldharaNanoti, Saraswati GirishPaesani, Giacomo2025-08-282025-08-282025-07-0110.48550/arXiv.2507.09283https://d8.irins.org/handle/IITG2025/19906We study the m-Eternal Domination problem, which is the following two-player game between a defender and an attacker on a graph: initially, the defender positions k guards on vertices of the graph; the game then proceeds in turns between the defender and the attacker, with the attacker selecting a vertex and the defender responding to the attack by moving a guard to the attacked vertex. The defender may move more than one guard on their turn, but guards can only move to neighboring vertices. The defender wins a game on a graph G with k guards if the defender has a strategy such that at every point of the game the vertices occupied by guards form a dominating set of G and the attacker wins otherwise. The m-eternal domination number of a graph G is the smallest value of k for which (G,k) is a defender win. We show that m-Eternal Domination is NP-hard, as well as some of its variants, even on special classes of graphs. We also show structural results for the Domination and m-Eternal Domination problems in the context of four types of infinite regular grids: square, octagonal, hexagonal, and triangular, establishing tight bounds.en-USEternal dominationRoman dominationItalian dominationNP-hardnessBipartite graphsSplit graphsInfinite gridse-Printe-Print123456789/435