Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination

Abolfazl Poureidi (), Mehrdad Ghaznavi () and Jafar Fathali ()
Additional contact information
Abolfazl Poureidi: Shahrood University of Technology
Mehrdad Ghaznavi: Shahrood University of Technology
Jafar Fathali: Shahrood University of Technology

Journal of Combinatorial Optimization, 2021, vol. 41, issue 2, No 3, 304-317

Abstract: Abstract Let $$G=(V,E)$$ G = ( V , E ) be a graph. A function $$f : V \rightarrow \{0, 1, 2\}$$ f : V → { 0 , 1 , 2 } is an outer independent Roman dominating function (OIRDF) on a graph G if for every vertex $$v \in V$$ v ∈ V with $$f (v) = 0$$ f ( v ) = 0 there is a vertex u adjacent to v with $$f (u) = 2$$ f ( u ) = 2 and $$\{x\in V:f(x)=0\}$$ { x ∈ V : f ( x ) = 0 } is an independent set. The weight of f is the value $$ f(V)=\sum _{v\in V}f(v)$$ f ( V ) = ∑ v ∈ V f ( v ) . An outer independent total Roman dominating function (OITRDF) f on G is an OIRDF on G such that for every $$v\in V$$ v ∈ V with $$f(v)>0$$ f ( v ) > 0 there is a vertex u adjacent to v with $$f (u)>0$$ f ( u ) > 0 . The minimum weight of an OIRDF on G is called the outer independent Roman domination number of G, denoted by $$\gamma _{oiR}(G)$$ γ oiR ( G ) . Similarly, the outer independent total Roman domination number of G is defined, denoted by $$\gamma _{oitR}(G)$$ γ oitR ( G ) . In this paper, we first show that computing $$\gamma _{oiR}(G)$$ γ oiR ( G ) (respectively, $$\gamma _{oitR}(G)$$ γ oitR ( G ) ) is a NP-hard problem, even when G is a chordal graph. Then, for a given proper interval graph $$G=(V,E)$$ G = ( V , E ) we propose an algorithm to compute $$\gamma _{oiR}(G)$$ γ oiR ( G ) (respectively, $$\gamma _{oitR}(G)$$ γ oitR ( G ) ) in $${\mathcal {O}}(|V| )$$ O ( | V | ) time.

Keywords: Outer independent Roman dominating function; Outer independent total Roman dominating function; Linear algorithm; Proper interval graph; NP-hard (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00682-1 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:41:y:2021:i:2:d:10.1007_s10878-020-00682-1

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

DOI: 10.1007/s10878-020-00682-1

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 ().