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

Weak Double Roman Domination

  • S. Soltani,
  • H. Abdollahzadeh Ahangar,
  • M. Chellali,
  • H. Rahbani,
  • S. M. Sheikholeslami

摘要

In this paper, we initiate the study of a variant less restrictive than double Roman dominating functions. Let \(G=(V,E)\) G = ( V , E ) be a graph and f a function defined from V(G) to \(\{0,1,2,3\}.\) { 0 , 1 , 2 , 3 } . A vertex v of G is said to be doubly unprotected with respect to f if \(f(N[v])\le 1,\) f ( N [ v ] ) 1 , where N[v] is a set consisting of vertex v and all vertices adjacent to v. The function f is said to be a weak double Roman dominating function (WDRD-function) if for every vertex v with \(f(v)\le 1\) f ( v ) 1 there is a neighbor u of v with \(f(u)\ge 2\) f ( u ) 2 such that the function g defined by \(g(v)=f(v)+1,\) g ( v ) = f ( v ) + 1 , \(g(u)=f(u)-1\) g ( u ) = f ( u ) - 1 and \(g(x)=f(x)\) g ( x ) = f ( x ) for all \(x\in V(G)-\{u,v\}\) x V ( G ) - { u , v } has no doubly unprotected vertex. The weight of a WDRD-function f is the sum \(\sum _{v\in V}f(v)\) v V f ( v ) , and the weak double Roman domination number equals the minimum weight of a WDRD-function on G. Sharp bounds involving the weak double Roman domination number with some (Roman) domination parameters are established. Moreover, we show that the weak double Roman domination number of a nontrivial connected graph G is bounded above by the order of G, and we establish the exact values of this parameter for paths, cycles and ladders. We also show that the associated decision problem is NP-complete, even for bipartite and chordal graphs.