On a Relation between the Perfect Roman Domination and Perfect Domination Numbers of a Tree

Zehui Shao, Saeed Kosari, Mustapha Chellali, Seyed Mahmoud Sheikholeslami and Marzieh Soroudi
Additional contact information
Zehui Shao: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Saeed Kosari: Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
Mustapha Chellali: LAMDA-RO Laboratory, Department of Mathematics, University of Blida, Blida B.P. 270, Algeria
Seyed Mahmoud Sheikholeslami: Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz 51368, Iran
Marzieh Soroudi: Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz 51368, Iran

Mathematics, 2020, vol. 8, issue 6, 1-13

Abstract: A dominating set in a graph G is a set of vertices S ⊆ V ( G ) such that any vertex of V − S is adjacent to at least one vertex of S . A dominating set S of G is said to be a perfect dominating set if each vertex in V − S is adjacent to exactly one vertex in S . The minimum cardinality of a perfect dominating set is the perfect domination number γ p ( G ) . A function f : V ( G ) → { 0 , 1 , 2 } is a perfect Roman dominating function (PRDF) on G if every vertex u ∈ V for which f ( u ) = 0 is adjacent to exactly one vertex v for which f ( v ) = 2 . The weight of a PRDF is the sum of its function values over all vertices, and the minimum weight of a PRDF of G is the perfect Roman domination number γ R p ( G ) . In this paper, we prove that for any nontrivial tree T , γ R p ( T ) ≥ γ p ( T ) + 1 and we characterize all trees attaining this bound.

Keywords: Roman domination number; perfect Roman domination number; tree (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/6/966/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/6/966/ (text/html)

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:gam:jmathe:v:8:y:2020:i:6:p:966-:d:370709

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().