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)