| Summary: | 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>.
|
|---|