Double Roman Graphs in P (3 k, k )

Zehui Shao, Rija Erveš, Huiqin Jiang, Aljoša Peperko, Pu Wu and Janez Žerovnik
Additional contact information
Zehui Shao: Research Institute of Intelligence Software, Guangzhou University, Guangzhou 510006, China
Rija Erveš: FCETEA, University of Maribor, Smetanova Ulica 17, SI-2000 Maribor, Slovenia
Huiqin Jiang: School of Information Science and Engineering, Chengdu University, Chengdu 610106, China
Aljoša Peperko: FME, University of Ljubljana, Aškerčeva 6, SI-1000 Ljubljana, Slovenia
Pu Wu: Research Institute of Intelligence Software, Guangzhou University, Guangzhou 510006, China
Janez Žerovnik: FME, University of Ljubljana, Aškerčeva 6, SI-1000 Ljubljana, Slovenia

Mathematics, 2021, vol. 9, issue 4, 1-18

Abstract: A double Roman dominating function on a graph G = ( V , E ) is a function f : V ? { 0 , 1 , 2 , 3 } with the properties that if f ( u ) = 0 , then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if f ( u ) = 1 , then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w ( f ) = ? v ? V f ( v ) . The double Roman domination number ? d R ( G ) of a graph G is the minimum weight of a double Roman dominating function of G . A graph is said to be double Roman if ? d R ( G ) = 3 ? ( G ) , where ? ( G ) is the domination number of G . We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs P ( 3 k , k ) , and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs P ( 3 k , k ) . This implies that P ( 3 k , k ) is a double Roman graph if and only if either k ? 0 (mod 3) or k ? { 1 , 4 } .

Keywords: double Roman domination; generalized Petersen graph; double Roman graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/336/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/336/ (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:9:y:2021:i:4:p:336-:d:495559

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