Opuscula Math. 33, no. 4 (2013), 641-646
http://dx.doi.org/10.7494/OpMath.2013.33.4.641

Opuscula Mathematica

# A note on k-Roman graphs

Ahmed Bouchou
Mostafa Blidia
Mustapha Chellali

Abstract. Let $$G=\left(V,E\right)$$ be a graph and let $$k$$ be a positive integer. A subset $$D$$ of $$V\left( G\right)$$ is a $$k$$-dominating set of $$G$$ if every vertex in $$V\left( G\right) \backslash D$$ has at least $$k$$ neighbours in $$D$$. The $$k$$-domination number $$\gamma_{k}(G)$$ is the minimum cardinality of a $$k$$-dominating set of $$G.$$ A Roman $$k$$-dominating function on $$G$$ is a function $$f\colon V(G)\longrightarrow\{0,1,2\}$$ such that every vertex $$u$$ for which $$f(u)=0$$ is adjacent to at least $$k$$ vertices $$v_{1},v_{2},\ldots ,v_{k}$$ with $$f(v_{i})=2$$ for $$i=1,2,\ldots ,k.$$ The weight of a Roman $$k$$-dominating function is the value $$f(V(G))=\sum_{u\in V(G)}f(u)$$ and the minimum weight of a Roman $$k$$-dominating function on $$G$$ is called the Roman $$k$$-domination number $$\gamma_{kR}\left( G\right)$$ of $$G$$. A graph $$G$$ is said to be a $$k$$-Roman graph if $$\gamma_{kR}(G)=2\gamma_{k}(G).$$ In this note we study $$k$$-Roman graphs.

Keywords: Roman $$k$$-domination, $$k$$-Roman graph.

Mathematics Subject Classification: 05C69.

Full text (pdf)

• Ahmed Bouchou
• University Dr Yahia Fares, Médéa, Algeria
• Mostafa Blidia
• University of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
• Mustapha Chellali
• LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
• Revised: 2013-02-25.
• Accepted: 2013-04-04. 