On perfect Roman domination number in trees: complexity and bounds

Mahsa Darkooti, Abdollah Alhevaz (), Sadegh Rahimi and Hadi Rahbani
Additional contact information
Mahsa Darkooti: Shahrood University of Technology
Abdollah Alhevaz: Shahrood University of Technology
Sadegh Rahimi: Shahrood University of Technology
Hadi Rahbani: Shahrood University of Technology

Journal of Combinatorial Optimization, 2019, vol. 38, issue 3, No 5, 712-720

Abstract: Abstract A perfect Roman dominating function on a graph $$G =(V,E)$$ G = ( V , E ) is a function $$f: V \longrightarrow \{0, 1, 2\}$$ f : V ⟶ { 0 , 1 , 2 } satisfying the condition that every vertex u with $$f(u) = 0$$ f ( u ) = 0 is adjacent to exactly one vertex v for which $$f(v)=2$$ f ( v ) = 2 . The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted by $$\gamma _{R}^{p}(G)$$ γ R p ( G ) , is the minimum weight of a perfect Roman dominating function in G. In this paper, we first show that the decision problem associated with $$\gamma _{R}^{p}(G)$$ γ R p ( G ) is NP-complete for bipartite graphs. Then, we prove that for every tree T of order $$n\ge 3$$ n ≥ 3 , with $$\ell $$ ℓ leaves and s support vertices, $$\gamma _R^P(T)\le (4n-l+2s-2)/5$$ γ R P ( T ) ≤ ( 4 n - l + 2 s - 2 ) / 5 , improving a previous bound given in Henning et al. (Discrete Appl Math 236:235–245, 2018).

Keywords: Dominating set; Roman dominating function; Perfect Roman dominating function; 05C69 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00408-y 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-00408-y

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

DOI: 10.1007/s10878-019-00408-y

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