Defending the Roman Empire---a new strategy (Q1810648): Difference between revisions

Let \(G= (V,E)\) be a graph and let \(f\) be a function \(f: V\to \{0,1,2\}\). A vertex \(u\) with \(f(u)= 0\) is undefended with respect to \(f\) if it is not adjacent to a vertex of positive weight. A function \(f\) is a weak Roman domination function if each \(u\in V\) with \(f(u)= 0\) is adjacent to a vertex \(v\) with \(f(v)> 0\) such that the function \(f': V\to\{0,1,2\}\) defined by \(f'(u)= 1\), \(f'(v)= f(v)- 1\) and \(f'(w)= f(w)\), \(w\in V- \{u,v\}\) has no undefended vertex. The weight of \(f\) is \(w(f)= \sum_{v\in V} f(v)\). The weak Roman domination number \(\gamma_r(G)\) is the minimum weight of a weak Roman domination function of \(G\). It is proved that \(\gamma(G)\leq \gamma_r(G)\leq 2\gamma(G)\) for every graph \(G\).