m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915385832374272 |
|---|---|
| author | Calamoneri, Tiziana Corò, Federico Misra, Neeldhara Nanoti, Saraswati G. Paesani, Giacomo |
| author_facet | Calamoneri, Tiziana Corò, Federico Misra, Neeldhara Nanoti, Saraswati G. Paesani, Giacomo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09283 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs Calamoneri, Tiziana Corò, Federico Misra, Neeldhara Nanoti, Saraswati G. Paesani, Giacomo Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics 05C85, 68R10 G.2.2 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. |
| title | m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics 05C85, 68R10 G.2.2 |
| url | https://arxiv.org/abs/2507.09283 |