Opuscula Math. 32, no. 4 (2012), 715-718
http://dx.doi.org/10.7494/OpMath.2012.32.4.715

Opuscula Mathematica

A note on the independent roman domination in unicyclic graphs

Mustapha Chellali

Abstract. A Roman dominating function (RDF) on a graph $$G = (V;E)$$ is a function $$f : V \to \{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 weight of an RDF is the value $$f(V(G)) = \sum _{u \in V (G)} f(u)$$. An RDF $$f$$ in a graph $$G$$ is independent if no two vertices assigned positive values are adjacent. The Roman domination number $$\gamma _R (G)$$ (respectively, the independent Roman domination number $$i_{R}(G)$$) is the minimum weight of an RDF (respectively, independent RDF) on $$G$$. We say that $$\gamma _R (G)$$ strongly equals $$i_R (G)$$, denoted by $$\gamma _R (G) \equiv i_R (G)$$, if every RDF on $$G$$ of minimum weight is independent. In this note we characterize all unicyclic graphs $$G$$ with $$\gamma _R (G) \equiv i_R (G)$$.

Keywords: Roman domination, independent Roman domination, strong equality.

Mathematics Subject Classification: 05C69.

Full text (pdf)

• Mustapha Chellali
• University of Blida, LAMDA-RO Laboratory, Department of Mathematics B.P. 270, Blida, Algeria
• Shahrood University of Technology, Department of Mathematics Shahrood, Iran
• Revised: 2012-05-02.
• Accepted: 2012-05-07.