{"ID":2895440,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.09283","arxiv_id":"2507.09283","title":"m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs","abstract":"We 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.","short_abstract":"We 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 defend...","url_abs":"https://arxiv.org/abs/2507.09283","url_pdf":"https://arxiv.org/pdf/2507.09283v1","authors":"[\"Tiziana Calamoneri\",\"Federico Corò\",\"Neeldhara Misra\",\"Saraswati G. Nanoti\",\"Giacomo Paesani\"]","published":"2025-07-12T13:43:19Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.CC\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}