Double Roman graphs in P(3k, k)

Shao, Zehui (author), Erveš, Rija (author), Jiang, Huiqin (author), Peperko, Aljoša (author), Wu, Pu (author), Žerovnik, Janez (author)

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 γ$_{dR}$(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 γ$_{dR}$(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(3k, 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(3k, k). This implies that P(3k, k) is a double Roman graph if and only if either k ≡ 0 (mod 3) or k ∈ {1, 4}.

• Language: English
• Keywords: double Roman domination, generalized Petersen graph, double Roman graph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: 18 str.
• Numbering: Vol. 9, iss. 4, art. 336
• PID: 20.500.12556/RUL-134471
• UDC: 519.17(045)
• ISSN on article: 2227-7390
• DOI: 10.3390/math9040336
• COBISS.SI-ID: 50563587
• Publication date in RUL: 17.01.2022

SHAO, Zehui, ERVEŠ, Rija, JIANG, Huiqin, PEPERKO, Aljoša, WU, Pu and ŽEROVNIK, Janez, 2021, Double Roman graphs in P(3k, k). Mathematics [online]. 2021. Vol. 9, no. 4,  336. [Accessed 11 April 2025]. DOI 10.3390/math9040336. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=134471

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 08.02.2021

Secondary language

• Language: Slovenian
• Keywords: dvojna rimska dominacija, posplošeni Petersenovi grafi, dvojno rimski grafi