Extremal digraphs for an upper bound on the Roman domination number

Lyes Ouldrabah (), Mostafa Blidia () and Ahmed Bouchou ()
Additional contact information
Lyes Ouldrabah: University of Blida 1
Mostafa Blidia: University of Blida 1
Ahmed Bouchou: University of Médéa

Journal of Combinatorial Optimization, 2019, vol. 38, issue 3, No 1, 667-679

Abstract: Abstract Let $$D=(V,A)$$ D = ( V , A ) be a digraph. A Roman dominating function of a digraph D is a function f : $$V\longrightarrow \{0,1,2\}$$ V ⟶ { 0 , 1 , 2 } such that every vertex u for which $$f(u)=0$$ f ( u ) = 0 has an in-neighbor v for which $$f(v)=2$$ f ( v ) = 2 . The weight of a Roman dominating function is the value $$f(V)=\sum _{u\in V}f(u)$$ f ( V ) = ∑ u ∈ V f ( u ) . The minimum weight of a Roman dominating function of a digraph D is called the Roman domination number of D, denoted by $$\gamma _{R}(D)$$ γ R ( D ) . In this paper, we characterize some special classes of oriented graphs, namely out-regular oriented graphs and tournaments satisfying $$\gamma _{R}(D)=n-\Delta ^{+}(D)+1$$ γ R ( D ) = n - Δ + ( D ) + 1 . Moreover, we characterize digraphs D for which the equality $$\gamma _{R}(D)+\gamma _{R}(\overline{D})=n+3$$ γ R ( D ) + γ R ( D ¯ ) = n + 3 holds, where $$\overline{D}$$ D ¯ is the complement of D. Finally, we prove that the problem of deciding whether an oriented graph D satisfies $$\gamma _{R}(D)=n-\Delta ^{+}(D)+1$$ γ R ( D ) = n - Δ + ( D ) + 1 is CO- $$\mathcal {NP}$$ NP -complete.

Keywords: Roman domination; Digraph; Oriented graph; Tournament; 05C20; 05C69 (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00401-5 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:38:y:2019:i:3:d:10.1007_s10878-019-00401-5

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

DOI: 10.1007/s10878-019-00401-5

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