Quantcast

On the signed Roman kk-domination: Complexity and thin torus graphs

Research paper by ZehuiShaoab, SandiKlavžarcde, ZepengLif, PuWub, JinXuf

Indexed on: 10 Nov '17Published on: 01 Dec '17Published in: Discrete Applied Mathematics



Abstract

A signed Roman k<math class="math"><mi is="true">k</mi></math>-dominating function on a graph G=(V(G),E(G))<math class="math"><mi is="true">G</mi><mo is="true">=</mo><mrow is="true"><mo is="true">(</mo><mi is="true">V</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">,</mo><mi is="true">E</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">)</mo></mrow></math> is a function f:V(G)→{−1,1,2}<math class="math"><mi is="true">f</mi><mo is="true">:</mo><mi is="true">V</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">→</mo><mrow is="true"><mo is="true">{</mo><mo is="true">−</mo><mn is="true">1</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">,</mo><mn is="true">2</mn><mo is="true">}</mo></mrow></math> such that (i) every vertex u<math class="math"><mi is="true">u</mi></math> with f(u)=−1<math class="math"><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><mo is="true">−</mo><mn is="true">1</mn></math> is adjacent to at least one vertex v<math class="math"><mi is="true">v</mi></math> with f(v)=2<math class="math"><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><mn is="true">2</mn></math> and (ii) ∑x∈N[w]f(x)≥k<math class="math"><msub is="true"><mrow is="true"><mo is="true">∑</mo></mrow><mrow is="true"><mi is="true">x</mi><mo is="true">∈</mo><mi is="true">N</mi><mrow is="true"><mo is="true">[</mo><mi is="true">w</mi><mo is="true">]</mo></mrow></mrow></msub><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">x</mi><mo is="true">)</mo></mrow><mo is="true">≥</mo><mi is="true">k</mi></math> holds for any vertex w<math class="math"><mi is="true">w</mi></math>. The weight of f<math class="math"><mi is="true">f</mi></math> is ∑u∈V(G)f(u)<math class="math"><msub is="true"><mrow is="true"><mo is="true">∑</mo></mrow><mrow is="true"><mi is="true">u</mi><mo is="true">∈</mo><mi is="true">V</mi><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></mrow></msub><mi is="true">f</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow></math>, the minimum weight of a signed Roman k<math class="math"><mi is="true">k</mi></math>-dominating function is the signed Roman k<math class="math"><mi is="true">k</mi></math>-domination number γsRk(G)<math class="math"><msubsup is="true"><mrow is="true"><mi is="true">γ</mi></mrow><mrow is="true"><mi is="true">s</mi><mi is="true">R</mi></mrow><mrow is="true"><mi is="true">k</mi></mrow></msubsup><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> of G<math class="math"><mi is="true">G</mi></math>. It is proved that determining the signed Roman k<math class="math"><mi is="true">k</mi></math>-domination number of a graph is NP-complete for k∈{1,2}<math class="math"><mi is="true">k</mi><mo is="true">∈</mo><mrow is="true"><mo is="true">{</mo><mn is="true">1</mn><mo is="true">,</mo><mn is="true">2</mn><mo is="true">}</mo></mrow></math>. Using a discharging method, the values γsR2(C3□Cn)<math class="math"><msubsup is="true"><mrow is="true"><mi is="true">γ</mi></mrow><mrow is="true"><mi is="true">s</mi><mi is="true">R</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msubsup><mrow is="true"><mo is="true">(</mo><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mn is="true">3</mn></mrow></msub><mspace width="0.16667em" is="true"></mspace><mo is="true">□</mo><mspace width="0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">)</mo></mrow></math> and γsR2(C4□Cn)<math class="math"><msubsup is="true"><mrow is="true"><mi is="true">γ</mi></mrow><mrow is="true"><mi is="true">s</mi><mi is="true">R</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msubsup><mrow is="true"><mo is="true">(</mo><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mn is="true">4</mn></mrow></msub><mspace width="0.16667em" is="true"></mspace><mo is="true">□</mo><mspace width="0.16667em" is="true"></mspace><msub is="true"><mrow is="true"><mi is="true">C</mi></mrow><mrow is="true"><mi is="true">n</mi></mrow></msub><mo is="true">)</mo></mrow></math> are determined for all n<math class="math"><mi is="true">n</mi></math>.