Repository logo
  • English
  • العربية
  • বাংলা
  • Català
  • Čeština
  • Deutsch
  • Ελληνικά
  • Español
  • Suomi
  • Français
  • Gàidhlig
  • हिंदी
  • Magyar
  • Italiano
  • Қазақ
  • Latviešu
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Srpski (lat)
  • Српски
  • Svenska
  • Türkçe
  • Yкраї́нська
  • Tiếng Việt
Log In
New user? Click here to register.Have you forgotten your password?
  1. Home
  2. IIT Gandhinagar
  3. Computer Science and Engineering
  4. CSE Publications
  5. m-Eternal domination and variants on some classes of finite and infinite graphs
 
  • Details

m-Eternal domination and variants on some classes of finite and infinite graphs

Source
arXiv
Date Issued
2025-07-01
DOI
10.48550/arXiv.2507.09283
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.
URI
https://d8.irins.org/handle/IITG2025/19906
Subjects
Eternal domination
Roman domination
Italian domination
NP-hardness
Bipartite graphs
Split graphs
Infinite grids
IITGN Knowledge Repository Developed and Managed by Library

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Privacy policy
  • End User Agreement
  • Send Feedback
Repository logo COAR Notify