Roman domination and Mycieleki's structure in graphs

Abstract

For a graph $G=(V,E)$, a function $f:V\to \{0,1,2\}$ is called Roman dominating function (RDF) if for any vertex $v$ with $f(v)=0$, there is at least one vertex $w$ in its neighborhood with $f(w)=2$. The weight of an RDF $f$ of $G$ is the value $f(V)={\sum }_{v\in V}f(v)$. The minimum weight of an RDF of $G$ is its Roman domination number and denoted by ${\gamma }_R(G)$. In this paper, we first show that ${\gamma }_R(G)+1\le {\gamma }_R(\mu (G))\le {\gamma }_R(G)+2$, where $\mu (G)$ is the Mycielekian graph of $G$, and then characterize the graphs achieving equality in these bounds. Then for any positive integer $m$, we compute the Roman domination number of the $m$-Mycieleskian ${\mu }_m(G)$ of a special Roman graph $G$ in terms on ${\gamma }_R(G)$. Finally we present several graphs to illustrate the discussed graphs.