×

Maximal Roman domination numbers in graphs. (English) Zbl 1373.05133

Let \(G=(V,E)\) be a simple graph. A Roman dominating function of \(G\) is a labeling \(f: V (G)\rightarrow \{0,1,2\}\) such that every vertex with label \(0\) has a neighbor with label \(2\). The Roman domination number \(\gamma_{\mathrm{R}}(G)\) of \(G\) is the minimum of \(\sum_{v\in V } f(v)\) over such functions. A maximal Roman dominating function on \(G\) is a Roman dominating function \(f\) such that \(V_0=\{w\in V(G)\mid f(w)=0\}\) is not a dominating set of \(G\). The maximal Roman domination number \(\gamma_{\mathrm{mR}}(G)\) is the minimum weight of an maximal Roman dominating function on \(G\). The authors present some sharp bounds for \(\gamma_{\mathrm{mR}}(G)\). For example for a graph without isolated vertices, \(\gamma_{\mathrm{mR}}(G)\leq \gamma_{\mathrm{R}}(G)+\delta(G)\). Also, they determine values of maximal Roman domination number of some graphs, such as, complete multipartite graphs, path and cycle graphs. The authors also study graphs \(G\) with large \(\gamma_{\mathrm{mR}}(G)\) and graphs \(G\) with \(\gamma_{\mathrm{mR}}(G)\leq \gamma_{\mathrm{R}}(G)+2\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)