On maximal Roman domination in graphs

Abstract

A Roman dominating function (RDF) for a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex u of G for which $f\left(u\right)=0$ is adjacent to at least one vertex v of G for which $f\left(v\right)=2$. The weight of a RDF f is the sum $f\left(V\right)=\sum _{v\in V}f\left(v\right)$, and the minimum weight of a RDF for G is the Roman domination number, ${\gamma }_R\left(G\right),$ of G. A maximal RDF for a graph G is a RDF f such that $V_0=\{w\in V|f(w)=0\}$ is not a dominating set of G. The maximal Roman domination number, ${\gamma }_{mR}\left(G\right),$ of a graph G equals the minimum weight of a maximal RDF for G. We first show that determining the number ${\gamma }_{mR}\left(G\right)$ for an arbitrary graph G is NP-complete even when restricted to bipartite or planar graphs. Then, we characterize connected graphs G such that ${\gamma }_{mR}\left(G\right)={\gamma }_R\left(G\right)$. We also provide a characterization of all trees T of order n such that ${\gamma }_{mR}\left(T\right)=n-2$.

Keywords:

• maximal Roman domination
• Roman domination

2000 AMS Subject Classification:

• 05C69

Acknowledgments

The authors are grateful to anonymous referees for their remarks and suggestions that helped improve the manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.