Double Roman Graphs in P(3k, k)

A double Roman dominating function on a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo>&...

Full description

Bibliographic Details
Main Authors:	Zehui Shao, Rija Erveš, Huiqin Jiang, Aljoša Peperko, Pu Wu, Janez Žerovnik
Format:	Article
Language:	English
Published:	MDPI AG 2021-02-01
Series:	Mathematics
Subjects:	double Roman domination generalized Petersen graph double Roman graph
Online Access:	https://www.mdpi.com/2227-7390/9/4/336

_version_	1797412836394139648
author	Zehui Shao Rija Erveš Huiqin Jiang Aljoša Peperko Pu Wu Janez Žerovnik
author_facet	Zehui Shao Rija Erveš Huiqin Jiang Aljoša Peperko Pu Wu Janez Žerovnik
author_sort	Zehui Shao
collection	DOAJ
description	A double Roman dominating function on a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a function <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>→</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>}</mo></mrow></semantics></math></inline-formula> with the properties that if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula>, then vertex <i>u</i> is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula>, then vertex <i>u</i> is adjacent to at least one vertex assigned 2 or 3. The weight of <i>f</i> equals <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>v</mi><mo>∈</mo><mi>V</mi></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. The double Roman domination number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>γ</mi><mrow><mi>d</mi><mi>R</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of a graph <i>G</i> is the minimum weight of a double Roman dominating function of <i>G</i>. A graph is said to be double Roman if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>γ</mi><mrow><mi>d</mi><mi>R</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mn>3</mn><mi>γ</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>γ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the domination number of <i>G</i>. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>3</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>, and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>3</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>. This implies that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>3</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a double Roman graph if and only if either <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≡</mo><mn>0</mn></mrow></semantics></math></inline-formula> (mod 3) or <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>∈</mo><mo>{</mo><mn>1</mn><mo>,</mo><mn>4</mn><mo>}</mo></mrow></semantics></math></inline-formula>.
first_indexed	2024-03-09T05:08:58Z
format	Article
id	doaj.art-54a58956a7744e21bd6f1f7053654716
institution	Directory Open Access Journal
issn	2227-7390
language	English
last_indexed	2024-03-09T05:08:58Z
publishDate	2021-02-01
publisher	MDPI AG
record_format	Article
series	Mathematics
spelling	doaj.art-54a58956a7744e21bd6f1f70536547162023-12-03T12:51:38ZengMDPI AGMathematics2227-73902021-02-019433610.3390/math9040336Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)Zehui Shao0Rija Erveš1Huiqin Jiang2Aljoša Peperko3Pu Wu4Janez Žerovnik5Research Institute of Intelligence Software, Guangzhou University, Guangzhou 510006, ChinaFCETEA, University of Maribor, Smetanova Ulica 17, SI-2000 Maribor, SloveniaSchool of Information Science and Engineering, Chengdu University, Chengdu 610106, ChinaFME, University of Ljubljana, Aškerčeva 6, SI-1000 Ljubljana, SloveniaResearch Institute of Intelligence Software, Guangzhou University, Guangzhou 510006, ChinaFME, University of Ljubljana, Aškerčeva 6, SI-1000 Ljubljana, SloveniaA double Roman dominating function on a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a function <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>→</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>}</mo></mrow></semantics></math></inline-formula> with the properties that if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>=</mo><mn>0</mn></mrow></semantics></math></inline-formula>, then vertex <i>u</i> is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>(</mo><mi>u</mi><mo>)</mo><mo>=</mo><mn>1</mn></mrow></semantics></math></inline-formula>, then vertex <i>u</i> is adjacent to at least one vertex assigned 2 or 3. The weight of <i>f</i> equals <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>v</mi><mo>∈</mo><mi>V</mi></mrow></msub><mi>f</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. The double Roman domination number <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>γ</mi><mrow><mi>d</mi><mi>R</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> of a graph <i>G</i> is the minimum weight of a double Roman dominating function of <i>G</i>. A graph is said to be double Roman if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>γ</mi><mrow><mi>d</mi><mi>R</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mn>3</mn><mi>γ</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>γ</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> is the domination number of <i>G</i>. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>3</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>, and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>3</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>. This implies that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>3</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula> is a double Roman graph if and only if either <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≡</mo><mn>0</mn></mrow></semantics></math></inline-formula> (mod 3) or <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>∈</mo><mo>{</mo><mn>1</mn><mo>,</mo><mn>4</mn><mo>}</mo></mrow></semantics></math></inline-formula>.https://www.mdpi.com/2227-7390/9/4/336double Roman dominationgeneralized Petersen graphdouble Roman graph
spellingShingle	Zehui Shao Rija Erveš Huiqin Jiang Aljoša Peperko Pu Wu Janez Žerovnik Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>) Mathematics double Roman domination generalized Petersen graph double Roman graph
title	Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)
title_full	Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)
title_fullStr	Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)
title_full_unstemmed	Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)
title_short	Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)
title_sort	double roman graphs in i p i 3 i k i i k i
topic	double Roman domination generalized Petersen graph double Roman graph
url	https://www.mdpi.com/2227-7390/9/4/336
work_keys_str_mv	AT zehuishao doubleromangraphsinipi3ikiiki AT rijaerves doubleromangraphsinipi3ikiiki AT huiqinjiang doubleromangraphsinipi3ikiiki AT aljosapeperko doubleromangraphsinipi3ikiiki AT puwu doubleromangraphsinipi3ikiiki AT janezzerovnik doubleromangraphsinipi3ikiiki

Double Roman Graphs in <i>P</i>(3<i>k</i>, <i>k</i>)

Similar Items