On the computational complexity of Roman $$\{2\}$$ { 2 } -domination in grid graphs

Aflatoun Amouzandeh () and Ahmad Moradi ()
Additional contact information
Aflatoun Amouzandeh: University of Siegen
Ahmad Moradi: University of Mazandaran

Journal of Combinatorial Optimization, 2023, vol. 45, issue 3, No 12, 10 pages

Abstract: Abstract A Roman $$\{2\}$$ { 2 } -dominating function of a graph $$G=(V,E)$$ G = ( V , E ) is a function $$f:V\rightarrow \{0,1,2\}$$ f : V → { 0 , 1 , 2 } such that every vertex $$x\in V$$ x ∈ V with $$f(x)=0$$ f ( x ) = 0 either there exists at least one vertex $$y\in N(x)$$ y ∈ N ( x ) with $$f(y)=2$$ f ( y ) = 2 or there are at least two vertices $$u,v\in N(x)$$ u , v ∈ N ( x ) with $$f(u)=f(v)=1$$ f ( u ) = f ( v ) = 1 . The weight of a Roman $$\{2\}$$ { 2 } -dominating function f on G is defined to be the value of $$\sum _{x\in V} f(x)$$ ∑ x ∈ V f ( x ) . The minimum weight of a Roman $$\{2\}$$ { 2 } -dominating function on G is called the Roman $$\{2\}$$ { 2 } -domination number of G. In this paper, we prove that the decision problem associated with Roman $$\{2\}$$ { 2 } -domination number is NP-complete even when restricted to subgraphs of grid graphs. Additionally, we answer an open question about the approximation hardness of Roman $$\{2\}$$ { 2 } -domination problem for bounded degree graphs.

Keywords: Computational complexity; Roman $$\{2\}$$ { 2 } -domination; APX-hardness; Grid graphs (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01024-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:3:d:10.1007_s10878-023-01024-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01024-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().