<p>The outer-independent signed Roman domination function (OISRDF) on <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\textit{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">G</mi> </math></EquationSource> </InlineEquation>=(<InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textit{V}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">V</mi> </math></EquationSource> </InlineEquation>,<InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textit{E}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">E</mi> </math></EquationSource> </InlineEquation>) is the mapping <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\textit{f}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">f</mi> </math></EquationSource> </InlineEquation>:<InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\textit{V}\rightarrow \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">V</mi> <mo stretchy="false">→</mo> </mrow> </math></EquationSource> </InlineEquation> {<InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\text {-1} {\textbf {, }}\text {1} {\textbf {, }}\text {2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>-1</mtext> <mo>,</mo> <mtext>1</mtext> <mo>,</mo> <mtext>2</mtext> </mrow> </math></EquationSource> </InlineEquation>}, which fulfills (i) for any <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\textit{w}\in \textit{V}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">w</mi> <mo>∈</mo> <mi mathvariant="italic">V</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\textit{f}(\textit{N}[\textit{w}])=\sum _{\textit{z} \in \textit{N}[\textit{w}]} \textit{f}(\textit{z}) \ge \text {1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">f</mi> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">N</mi> <mrow> <mo stretchy="false">[</mo> <mi mathvariant="italic">w</mi> <mo stretchy="false">]</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mo>∑</mo> <mrow> <mi mathvariant="italic">z</mi> <mo>∈</mo> <mi mathvariant="italic">N</mi> <mo stretchy="false">[</mo> <mi mathvariant="italic">w</mi> <mo stretchy="false">]</mo> </mrow> </msub> <mi mathvariant="italic">f</mi> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">z</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mtext>1</mtext> </mrow> </math></EquationSource> </InlineEquation>; (ii) a vertex with function value <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\text {-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mtext>-1</mtext> </math></EquationSource> </InlineEquation> is contiguous to a minimum of vertex with function value <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\text {2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mtext>2</mtext> </math></EquationSource> </InlineEquation>; (iii) all vertices labeled by <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\text {-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mtext>-1</mtext> </math></EquationSource> </InlineEquation> is independent. The weight of OISRDF <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\textit{f}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">f</mi> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\textit{w} {\textbf {(}} \textit{f} {\textbf {)}}=\sum _{\textit{v}\in \textit{V}}=-|\textit{V}_{\text {-1}}|+|\textit{V}_{\text {1}}|+\text {2}|\textit{V}_{\text {2}}|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">w</mi> <mo stretchy="false">(</mo> <mi mathvariant="italic">f</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mo>∑</mo> <mrow> <mi mathvariant="italic">v</mi> <mo>∈</mo> <mi mathvariant="italic">V</mi> </mrow> </msub> <mrow> <mo>=</mo> <mo>-</mo> <mo stretchy="false">|</mo> </mrow> <msub> <mi mathvariant="italic">V</mi> <mtext>-1</mtext> </msub> <mrow> <mo stretchy="false">|</mo> <mo>+</mo> <mo stretchy="false">|</mo> </mrow> <msub> <mi mathvariant="italic">V</mi> <mtext>1</mtext> </msub> <mrow> <mo stretchy="false">|</mo> <mo>+</mo> <mtext>2</mtext> <mo stretchy="false">|</mo> </mrow> <msub> <mi mathvariant="italic">V</mi> <mtext>2</mtext> </msub> <mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\textit{V}_{\text {i}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="italic">V</mi> <mtext>i</mtext> </msub> </math></EquationSource> </InlineEquation>={<InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\textit{v}\in \textit{V} {\textbf {: }} \textit{f} {\textbf {(}} \textit{v} {\textbf {)}}={i}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="italic">v</mi> <mo>∈</mo> <mi mathvariant="italic">V</mi> <mo>:</mo> <mi mathvariant="italic">f</mi> <mo stretchy="false">(</mo> <mi mathvariant="italic">v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>i</mi> </mrow> </math></EquationSource> </InlineEquation>},<InlineEquation ID="IEq16"> <EquationSource Format="TEX">\({i}\in \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> </mrow> </math></EquationSource> </InlineEquation>{<InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\text {-1} {\textbf {, }}\text {1} {\textbf {, }}\text {2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>-1</mtext> <mo>,</mo> <mtext>1</mtext> <mo>,</mo> <mtext>2</mtext> </mrow> </math></EquationSource> </InlineEquation>}. The outer-independent signed Roman domination number <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\({\gamma ^{\textit{oi}}_{\textit{sR}} \textit{(G)}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi mathvariant="italic">sR</mi> <mi mathvariant="italic">oi</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the minimal weight OISRDF <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(\textit{f}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">f</mi> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(\textit{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">G</mi> </math></EquationSource> </InlineEquation>. Initially, we establish the relationship between <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(|{\textit{V}_{\text {-1}}} |\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msub> <mi mathvariant="italic">V</mi> <mtext>-1</mtext> </msub> <mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(|\textit{V}_\textit{2} |\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msub> <mi mathvariant="italic">V</mi> <mn mathvariant="italic">2</mn> </msub> <mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in a general graph. Furthermore, we provide some bounds for the OISRDF in paths, complete graphs, and complete bipartite graphs. Then, we demonstrate that the problem of OISRDF is NP-complete on bipartite and chordal graphs. Finally, we validate the upper bounds for the&#xa0;<InlineEquation ID="IEq23"> <EquationSource Format="TEX">\({\gamma ^{\textit{oi}}_{\textit{sR}} \textit{(P}_{\textit{m}} \times \textit{P}_{\textit{n}} \textit{)}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi mathvariant="italic">sR</mi> <mi mathvariant="italic">oi</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi mathvariant="italic">P</mi> <mi mathvariant="italic">m</mi> </msub> <mo>×</mo> <msub> <mi mathvariant="italic">P</mi> <mi mathvariant="italic">n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of the Cartesian product graphs <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(\textit{P}_{\textit{m}} \times \textit{P}_{\textit{n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="italic">P</mi> <mi mathvariant="italic">m</mi> </msub> <mo>×</mo> <msub> <mi mathvariant="italic">P</mi> <mi mathvariant="italic">n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, leveraging the parity differences between <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\(\textit{m}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">m</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(\textit{n}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="italic">n</mi> </math></EquationSource> </InlineEquation> in the <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(\textit{P}_{\textit{m}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="italic">P</mi> <mi mathvariant="italic">m</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\(\textit{P}_{\textit{n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="italic">P</mi> <mi mathvariant="italic">n</mi> </msub> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Outer-Independent Signed Roman Domination Function in Graphs

  • Ning Li,
  • Peng Li,
  • Jianhui Shang

摘要

The outer-independent signed Roman domination function (OISRDF) on \(\textit{G}\) G =( \(\textit{V}\) V , \(\textit{E}\) E ) is the mapping \(\textit{f}\) f : \(\textit{V}\rightarrow \) V { \(\text {-1} {\textbf {, }}\text {1} {\textbf {, }}\text {2}\) -1 , 1 , 2 }, which fulfills (i) for any \(\textit{w}\in \textit{V}\) w V , \(\textit{f}(\textit{N}[\textit{w}])=\sum _{\textit{z} \in \textit{N}[\textit{w}]} \textit{f}(\textit{z}) \ge \text {1}\) f ( N [ w ] ) = z N [ w ] f ( z ) 1 ; (ii) a vertex with function value \(\text {-1}\) -1 is contiguous to a minimum of vertex with function value \(\text {2}\) 2 ; (iii) all vertices labeled by \(\text {-1}\) -1 is independent. The weight of OISRDF \(\textit{f}\) f is \(\textit{w} {\textbf {(}} \textit{f} {\textbf {)}}=\sum _{\textit{v}\in \textit{V}}=-|\textit{V}_{\text {-1}}|+|\textit{V}_{\text {1}}|+\text {2}|\textit{V}_{\text {2}}|\) w ( f ) = v V = - | V -1 | + | V 1 | + 2 | V 2 | where \(\textit{V}_{\text {i}}\) V i ={ \(\textit{v}\in \textit{V} {\textbf {: }} \textit{f} {\textbf {(}} \textit{v} {\textbf {)}}={i}\) v V : f ( v ) = i }, \({i}\in \) i { \(\text {-1} {\textbf {, }}\text {1} {\textbf {, }}\text {2}\) -1 , 1 , 2 }. The outer-independent signed Roman domination number \({\gamma ^{\textit{oi}}_{\textit{sR}} \textit{(G)}}\) γ sR oi ( G ) is the minimal weight OISRDF \(\textit{f}\) f of \(\textit{G}\) G . Initially, we establish the relationship between \(|{\textit{V}_{\text {-1}}} |\) | V -1 | and \(|\textit{V}_\textit{2} |\) | V 2 | in a general graph. Furthermore, we provide some bounds for the OISRDF in paths, complete graphs, and complete bipartite graphs. Then, we demonstrate that the problem of OISRDF is NP-complete on bipartite and chordal graphs. Finally, we validate the upper bounds for the  \({\gamma ^{\textit{oi}}_{\textit{sR}} \textit{(P}_{\textit{m}} \times \textit{P}_{\textit{n}} \textit{)}}\) γ sR oi ( P m × P n ) of the Cartesian product graphs \(\textit{P}_{\textit{m}} \times \textit{P}_{\textit{n}}\) P m × P n , leveraging the parity differences between \(\textit{m}\) m and \(\textit{n}\) n in the \(\textit{P}_{\textit{m}}\) P m and \(\textit{P}_{\textit{n}}\) P n .