A note on Roman domination in graphs (Q856892)

The main result of the paper is the solution of the problem about a characterization of simple graphs for which \(\gamma_{R}(G) = \gamma(G) + k\) [\textit{E. J. Cockayne} et al., Discrete Math. 278, 11--22 (2004; Zbl 1036.05034)]. Let \(G\) be a connected graph of order \(n\) with the domination number \(\gamma(G) \geq 2.\) The authors of the paper under review give necessary and sufficient conditions for the equality \(\gamma_{R}(G) = \gamma(G) + k\). Here \(\gamma_{R}(G)\) is the Roman domination number of \(G\) and \(k\) is an integer such that \( 2 \leq k \leq \gamma(G).\) A Roman dominating function on a graph \(G = (V,E)\) is a function \(f : V \rightarrow \{0, 1, 2\} \) satisfying the condition that every vertex \(u\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) for which \(f(v) = 2.\) The idea is that numbers \(1\) and \(2\) represent either one or two Roman legions stationed at a given location (vertex \(v\)). The weight of a Roman dominating function is the sum of the values \(f(v)\) where \(v\) runs over all \(V.\) The minimum weight of a Roman dominating function on a graph \(G\) is called the Roman domination number of \(G.\) The definition of a Roman dominating function is given implicitly in [\textit{J. Arquilla} and \textit{H. Fredricksen}, Military Operations Research 1 , 3--17 (1995)].