| Summary: | For a graph <inline-formula> <math 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> with vertex set <inline-formula> <math display="inline"> <semantics> <mrow> <mi>V</mi> <mo>=</mo> <mi>V</mi> <mo>(</mo> <mi>G</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> and edge set <inline-formula> <math display="inline"> <semantics> <mrow> <mi>E</mi> <mo>=</mo> <mi>E</mi> <mo>(</mo> <mi>G</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula>, a Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-dominating function (R<inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-DF) is a function <inline-formula> <math display="inline"> <semantics> <mrow> <mi>f</mi> <mo>:</mo> <mi>V</mi> <mo>(</mo> <mi>G</mi> <mo>)</mo> <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> having the property that <inline-formula> <math display="inline"> <semantics> <mrow> <msub> <mo>∑</mo> <mrow> <mi>u</mi> <mo>∈</mo> <msub> <mi>N</mi> <mi>G</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </mrow> </msub> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>≥</mo> <mn>3</mn> </mrow> </semantics> </math> </inline-formula>, if <inline-formula> <math display="inline"> <semantics> <mrow> <mi>f</mi> <mo>(</mo> <mi>v</mi> <mo>)</mo> <mo>=</mo> <mn>0</mn> </mrow> </semantics> </math> </inline-formula>, and <inline-formula> <math display="inline"> <semantics> <mrow> <msub> <mo>∑</mo> <mrow> <mi>u</mi> <mo>∈</mo> <msub> <mi>N</mi> <mi>G</mi> </msub> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </mrow> </msub> <mi>f</mi> <mrow> <mo>(</mo> <mi>u</mi> <mo>)</mo> </mrow> <mo>≥</mo> <mn>2</mn> </mrow> </semantics> </math> </inline-formula>, if <inline-formula> <math display="inline"> <semantics> <mrow> <mi>f</mi> <mo>(</mo> <mi>v</mi> <mo>)</mo> <mo>=</mo> <mn>1</mn> </mrow> </semantics> </math> </inline-formula> for any vertex <inline-formula> <math display="inline"> <semantics> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo>(</mo> <mi>G</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula>. The weight of a Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-dominating function <i>f</i> is the sum <inline-formula> <math display="inline"> <semantics> <mrow> <mi>f</mi> <mrow> <mo>(</mo> <mi>V</mi> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mo>∑</mo> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo>(</mo> <mi>G</mi> <mo>)</mo> </mrow> </msub> <mi>f</mi> <mrow> <mo>(</mo> <mi>v</mi> <mo>)</mo> </mrow> </mrow> </semantics> </math> </inline-formula> and the minimum weight of a Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-dominating function on <i>G</i> is the Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-domination number of <i>G</i>, denoted by <inline-formula> <math display="inline"> <semantics> <mrow> <msub> <mi>γ</mi> <mrow> <mo>{</mo> <mi>R</mi> <mn>3</mn> <mo>}</mo> </mrow> </msub> <mrow> <mo>(</mo> <mi>G</mi> <mo>)</mo> </mrow> </mrow> </semantics> </math> </inline-formula>. Let <i>G</i> be a graph with no isolated vertices. The total Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-dominating function on <i>G</i> is an R<inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-DF <i>f</i> on <i>G</i> with the additional property that every vertex <inline-formula> <math display="inline"> <semantics> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> </mrow> </semantics> </math> </inline-formula> with <inline-formula> <math display="inline"> <semantics> <mrow> <mi>f</mi> <mo>(</mo> <mi>v</mi> <mo>)</mo> <mo>≠</mo> <mn>0</mn> </mrow> </semantics> </math> </inline-formula> has a neighbor <i>w</i> with <inline-formula> <math display="inline"> <semantics> <mrow> <mi>f</mi> <mo>(</mo> <mi>w</mi> <mo>)</mo> <mo>≠</mo> <mn>0</mn> </mrow> </semantics> </math> </inline-formula>. The minimum weight of a total Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-dominating function on <i>G</i>, is called the total Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-domination number denoted by <inline-formula> <math display="inline"> <semantics> <mrow> <msub> <mi>γ</mi> <mrow> <mi>t</mi> <mo>{</mo> <mi>R</mi> <mn>3</mn> <mo>}</mo> </mrow> </msub> <mrow> <mo>(</mo> <mi>G</mi> <mo>)</mo> </mrow> </mrow> </semantics> </math> </inline-formula>. We initiate the study of total Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-domination and show its relationship to other domination parameters. We present an upper bound on the total Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-domination number of a connected graph <i>G</i> in terms of the order of <i>G</i> and characterize the graphs attaining this bound. Finally, we investigate the complexity of total Roman <inline-formula> <math display="inline"> <semantics> <mrow> <mo>{</mo> <mn>3</mn> <mo>}</mo> </mrow> </semantics> </math> </inline-formula>-domination for bipartite graphs.
|
|---|