pith. sign in

arxiv: 1105.3290 · v1 · pith:DURFL77Znew · submitted 2011-05-17 · 🧮 math.CO

Roman domination and Mycieleki's structure in graphs

classification 🧮 math.CO
keywords gammaromangraphsdominationgraphfunctionnumberthen
0
0 comments X
read the original abstract

For a graph $G=(V,E)$, a function $f:V\rightarrow \{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\leq \gamma_{R}(\mu (G))\leq \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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.