On the Double Roman Domination in Generalized Petersen Graphs P(5k,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:	Darja Rupnik Poklukar, Janez Žerovnik
Format:	Article
Language:	English
Published:	MDPI AG 2022-01-01
Series:	Mathematics
Subjects:	double Roman domination generalized Petersen graph discharging method graph cover double Roman graph
Online Access:	https://www.mdpi.com/2227-7390/10/1/119

_version_	1797498334198366208
author	Darja Rupnik Poklukar Janez Žerovnik
author_facet	Darja Rupnik Poklukar Janez Žerovnik
author_sort	Darja Rupnik Poklukar
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> satisfying the condition that every vertex <i>u</i> for which <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> is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex <i>u</i> with <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> 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> equals the minimum weight of a double Roman dominating function of <i>G</i>. We obtain closed expressions for 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>5</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>. It is proven that <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>P</mi><mrow><mo>(</mo><mn>5</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>=</mo><mn>8</mn><mi>k</mi></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≡</mo><mn>2</mn><mo>,</mo><mn>3</mn><mspace width="0.277778em"></mspace><mo form="prefix">mod</mo><mspace width="0.277778em"></mspace><mn>5</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>8</mn><mi>k</mi><mo>≤</mo><msub><mi>γ</mi><mrow><mi>d</mi><mi>R</mi></mrow></msub><mrow><mo>(</mo><mi>P</mi><mrow><mo>(</mo><mn>5</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>≤</mo><mn>8</mn><mi>k</mi><mo>+</mo><mn>2</mn></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≡</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>4</mn><mspace width="0.277778em"></mspace><mo form="prefix">mod</mo><mspace width="0.277778em"></mspace><mn>5</mn></mrow></semantics></math></inline-formula>. We also improve the upper bounds for generalized Petersen graphs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>20</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>.
first_indexed	2024-03-10T03:32:00Z
format	Article
id	doaj.art-8f556904ef3a4e55a1f16cc7f9b1f223
institution	Directory Open Access Journal
issn	2227-7390
language	English
last_indexed	2024-03-10T03:32:00Z
publishDate	2022-01-01
publisher	MDPI AG
record_format	Article
series	Mathematics
spelling	doaj.art-8f556904ef3a4e55a1f16cc7f9b1f2232023-11-23T11:54:25ZengMDPI AGMathematics2227-73902022-01-0110111910.3390/math10010119On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)Darja Rupnik Poklukar0Janez Žerovnik1Faculty of Mechanical Engineering, University of Ljubljana, Aškerčeva 6, 1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, University of Ljubljana, Aškerčeva 6, 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> satisfying the condition that every vertex <i>u</i> for which <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> is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex <i>u</i> with <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> 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> equals the minimum weight of a double Roman dominating function of <i>G</i>. We obtain closed expressions for 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>5</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>. It is proven that <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>P</mi><mrow><mo>(</mo><mn>5</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>=</mo><mn>8</mn><mi>k</mi></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≡</mo><mn>2</mn><mo>,</mo><mn>3</mn><mspace width="0.277778em"></mspace><mo form="prefix">mod</mo><mspace width="0.277778em"></mspace><mn>5</mn></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>8</mn><mi>k</mi><mo>≤</mo><msub><mi>γ</mi><mrow><mi>d</mi><mi>R</mi></mrow></msub><mrow><mo>(</mo><mi>P</mi><mrow><mo>(</mo><mn>5</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>≤</mo><mn>8</mn><mi>k</mi><mo>+</mo><mn>2</mn></mrow></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≡</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>4</mn><mspace width="0.277778em"></mspace><mo form="prefix">mod</mo><mspace width="0.277778em"></mspace><mn>5</mn></mrow></semantics></math></inline-formula>. We also improve the upper bounds for generalized Petersen graphs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>(</mo><mn>20</mn><mi>k</mi><mo>,</mo><mi>k</mi><mo>)</mo></mrow></semantics></math></inline-formula>.https://www.mdpi.com/2227-7390/10/1/119double Roman dominationgeneralized Petersen graphdischarging methodgraph coverdouble Roman graph
spellingShingle	Darja Rupnik Poklukar Janez Žerovnik On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>) Mathematics double Roman domination generalized Petersen graph discharging method graph cover double Roman graph
title	On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)
title_full	On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)
title_fullStr	On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)
title_full_unstemmed	On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)
title_short	On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)
title_sort	on the double roman domination in generalized petersen graphs i p i 5 i k i i k i
topic	double Roman domination generalized Petersen graph discharging method graph cover double Roman graph
url	https://www.mdpi.com/2227-7390/10/1/119
work_keys_str_mv	AT darjarupnikpoklukar onthedoubleromandominationingeneralizedpetersengraphsipi5ikiiki AT janezzerovnik onthedoubleromandominationingeneralizedpetersengraphsipi5ikiiki

On the Double Roman Domination in Generalized Petersen Graphs <i>P</i>(5<i>k</i>,<i>k</i>)

Similar Items