A note on k-Roman graphs

Abstract

Let $G=(V,E)$ be a graph and let $k$ be a positive integer. A subset $D$ of $V(G)$ 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.