On roman domination number of functigraph and its complement

Abstract

Let $G=(V(G),E(G))$ be a graph and $f:V(G)\to \{0,1,2\}$ be a function where for every vertex $v\in V(G)$ with $f(v)=0,$ there is a vertex $u\in N_G(v),$ where $f(u)=2.$ Then $f$ is a Roman dominating function or a $RDF$ of $G.$ The weight of $f$ is $f(V(G))={\sum }_{v\in V(G)}f(v).$ The minimum weight of all $RDF$ is called the Roman domination number of $G,$ denoted by ${\gamma }_R(G).$ Let $G$ be a graph with $V(G)=\{v_1,v_2,\dots ,v_n\}$ and G' be a copy of $G$ with $V(G^{\prime })=\{{v_1}^{\prime },{v_2}^{\prime },\dots ,{v_n}^{\prime }\}.$ Then a functigraph $G$ with function $\sigma :V(G)\to V(G^{\prime })$ is denoted by $C(G,\sigma ),$ its vertices and edges are $V(C(G,\sigma ))=V(G)\cup V(G^{\prime })$ and $E(C(G,\sigma ))=E(G)\cup E(G^{\prime })\cup \{v\sim v^{\prime }|v\in V(G),v^{\prime }\in V(G^{\prime }),\sigma (v)=v^{\prime }\},$ respectively. This paper deals with the Roman domination number of the functigraph and its complement. We present a general bound ${\gamma }_R(G)\le {\gamma }_R(C(G,\sigma ))\le 2{\gamma }_R(G),$ where $\sigma :V(G)\to V(G^{\prime })$ is a permutation. Also, the Roman domination number of some special graphs are considered. We obtain a general bound of ${\gamma }_R(\overline{C(G,\sigma )}$ and we show that this bound is sharp.

Keywords:

• Roman domination number
• functigraph
• complement
• cubic graph

PUBLIC INTEREST STATEMENT

Roman domination number is one of the interesting research areas in graph theory. The concept Roman dominating function was first defined by Cockayne, Dreyer, Hedetniemi and Hedetniemi and was motivated by an article in Scientific American by Ian Stewart entitled “Defend the Roman Empire”. The Roman domination number has been used in order to defending the Roman Empire that has the potential of saving the Emperor Constantine the Great substantial costs of maintaining legions, while still defending the Roman Empire.

1. Introduction

Let $G=(V(G),E(G))$ be a simple, finite, and undirected graph. The open neighborhood of a vertex $v\in V(G)$, denoted by $N_G(v)$, is the set of vertices adjacent to $v$ in $G.$ If two vertices $x$ and $y$ are adjacent, then it denoted by $x\sim y,$ otherwise, $x\nsim y.$ The closed neighborhood of a vertex $v$ is $G$ is $N_G[v]=N_G(v)\cup \{v\}.$ The degree of a vertex $v\in V(G)$ is $o_G(v)=|N_G(v)|$. The maximum degree and minimum degree are denoted by $\mathrm{\Delta }(G)$ and $\delta (G),$ respectively. A vertex is called universal vertex if its degree is $|V(G)|-1.$

The complement of graph $G$ is denoted by $\bar{G}$ is a graph with vertex set $V(G)$ which $e\in E(\bar{G})$ if and only if $e\notin E(G).$ For any $S\subseteq V(G),$ the induced subgraph on $S,$ denoted by $G[S].$

A subset $S$ of graph $G$ is a dominating set of $G$ if every vertex in $V(G)\mathrm{\setminus }S$ is adjacent to at least one vertex in $S.$ The domination number of a graph $G,$ denoted by $\gamma (G),$ is the minimum size of a dominating set of $G.$

Let $G$ and $H$ be two graphs on $n$ and $m$ vertices, respectively. The corona of the graphs $G$ and $H$ denoted by $G\circ H$ and is defined as the graph obtained by taking one copy of $G$ and $n$ copies of $H,$ and then joining the $i$-th vertex of $G$ to every vertex in the $i$-th copy of $H.$

Let $f:V(G)\to \{0,1,2\}$ be a function and let $(V_0,V_1,V_2)$ be the ordered partition of $V$ induced by $f,$ where $V_i=\{v\in V(G)|f(v)=i\}$ and $|V_i|=n_i,$ for $i=0,1,2.$ We notice that there is an obvious one-to-one correspondence between $f$ and the ordered partition $(V_0,V_1,V_2)$ of $V.$ Therefore, one can write $f=(V_0,V_1,V_2).$ Function $f=(V_0,V_1,V_2)$ is a Roman dominating function, abbreviated $RDF,$ for $G$ if $V_0\subseteq N_G(V_2).$ The weight of function $f$ is the value $f(V(G))={\sum }_{v\in V(G)}f(v)=2n_2+n_1.$ The Roman domination number ${\gamma }_R(G)$ is the minimum weight of an $RDF$ of $G,$ and we say a function $f=(V_0,V_1,V_2)$ is a ${\gamma }_R$—or ${\gamma }_R(G)$-function if it is an $RDF$ for $G$ and $f(V(G))={\gamma }_R(G).$ For more details, reader can see (Chambers et al., 2009; Favaron et al., 2009; Hajian & Rad, 2017; Kazemi, 2012; Rad & Volkmann, 2011; Ramezani et al., 2017).

Let $G$ be a graph with $V(G)=\{v_1,v_2,\dots ,v_n\}$ and $G^{\prime }$ be a copy of $G$ with $V(G^{\prime })=\{{v_1}^{\prime },{v_2}^{\prime },\dots ,{v_n}^{\prime }\}.$ Then a functigraph $G$ with function $\sigma :V(G)\to V(G^{\prime })$ is denoted by $C(G,\sigma ),$ its vertices and edges are $V(C(G,\sigma ))=V(G)\cup V(G^{\prime })$ and $E(C(G,\sigma ))=E(G)\cup E(G^{\prime })\cup \{v\sim v^{\prime }|v\in V(G),v^{\prime }\in V(G^{\prime }),\sigma (v)=v^{\prime }\},$ respectively. Throughout this paper, for every $v\in V(G)$ the vertex of $v^{\prime }\in V(G^{\prime })$ is corresponding to $v.$ For $v^{\prime }\in V(G^{\prime }),$ $R_{v^{\prime }}={\sigma }^{-1}(v^{\prime })=\{v\in V(G)|\sigma (v)=v^{\prime }\}$ and for $\mathrm{\ell }\in \{0,1,2,\cdots ,n=|V(G)|\},$ we define $B_{\mathrm{\ell }}=\{v^{\prime }\in V(G^{\prime })||R_{v^{\prime }}|=\mathrm{\ell }\}.$ For simplicity, the open neighborhood of $x$ in $C(G,\sigma )$ is denoted by $N_C(x).$

In $1969,$ Hedetniemi introduced two graphs with a function such that related these two graphs and he called it a “function graph” (Hedetniemi, 1969). Later, in (Chen et al., 2011), by Chen et al. this function is called functigraph, rediscovered, and studied. Also, in $2012$ the concept of domination number of functigraph was studied by Eroh et al. (Eroh et al., 2012).

This paper deals with the Roman domination number of the functigraph and its complement. For this aim, in section $2,$ we present a general bound ${\gamma }_R(G)\le {\gamma }_R(C(G,\sigma ))\le 2{\gamma }_R(G),$ where $\sigma :V(G)\to V(G^{\prime })$ is a permutation. In section $3,$ the Roman domination number of some special graphs are considered. Also, we obtain a general bound of ${\gamma }_R(\overline{C(G,\sigma )}$ and we show that this bound is sharp.

2. Roman domination number of$C\mathit{(}G\mathit{,}\sigma \mathit{)}$

In this section, we introduce a bound for Roman domination number of $C(G,\sigma )$ and calculate the exact value of Roman domination number of functigraphs of some special graphs. For investigating the Roman domination number of functigraph, the following basic properties are useful.

Theorem 1. (Ore, 1965) If $G$ has minimum degree $1,$ then $\gamma (G)\le \frac{\text{parallwl}\mid V(G)\mid }{2}.$

Theorem 2. (Fink et al., 1985) For a graph $G$ with even order $n$ and no any isolated vertices, $\gamma (G)=\frac{n}{2}$ if and only if the components of $G$ are the cycle $C_4$ or the corona $H\circ K_1$ for any connected graph $H.$

Proposition 3. (Cockayne et al., 2004) For any graph $G$ of order $n\ge 2$ and maximum degree $\mathrm{\Delta }(G),$ ${\gamma }_R(G)\ge \frac{2n}{\mathrm{\Delta }(G)+1}.$

Proposition 4. (Cockayne et al., 2004) For the classes of paths $P_n$ and cycles $C_n,$ ${\gamma }_R(P_n)={\gamma }_R(C_n)=\lceil \frac{2n}{3}\rceil .$

Lemma 5. Let $G$ be a graph of order $n.$ Then

i) ${\gamma }_R(G)=1$ if and only if $n=1.$

ii) ${\gamma }_R(G)=2$ if and only if $\mathrm{\Delta }(G)=n-1.$

iii) ${\gamma }_R(G)=3$ if and only if $\mathrm{\Delta }(G)=n-2.$

Proof. i)Let ${\gamma }_R(G)=1$ and $n\ge 2.$ By Proposition 3, $1\ge \frac{2n}{\mathrm{\Delta }(G)+1}.$ Since $\mathrm{\Delta }(G)\le n-1,$ so $2n\le n.$ Which is false.

ii) Let ${\gamma }_R(G)=2.$ By Proposition 3, $\frac{2n}{\mathrm{\Delta }(G)+1}\le 2$ and so $\mathrm{\Delta }(G)=n-1.$

Conversely, let $\mathrm{\Delta }(G)=n-1$ and $a$ be an universal vertex of $G.$ We define $f:V(G)\to \{0,1,2\},$ such that

$f(x)=\left\{\begin{array}{cc}2,& x=a\\ 0& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

Then $f$ is a $RDF$ of $G.$ So ${\gamma }_R(G)\le 2.$ By item $(i),$ ${\gamma }_R(G)=2.$

iii) Assume that ${\gamma }_R(G)=3$ and $f$ be a ${\gamma }_R$-function. Then, there are $a$ and $b$ in $V(G),$ such that $f(a)=2$ and $f(b)=1.$ So $V(G)\mathrm{\setminus }\{a,b\}\subseteq N_G(a).$ By item $(ii),$ $G$ does not have any universal vertex. Hence, $de{g}_G(a)=n-2$ and so $\mathrm{\Delta }(G)=n-2.$

Conversely, let $\mathrm{\Delta }(G)=n-2$ and $a\in V(G),$ with $de{g}_G(a)=n-2.$ Assume that $b\mathit{/}\in N_G(a)$ We define $f:V(G)\to \{0,1,2\},$ as

$f(x)=\left\{\begin{array}{cc}2,& x=a\\ 1,& x=b\\ 0& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

It is clear that $f$ is a $RDF$ of $G$ and so ${\gamma }_R(G)\le 3.$ By item $(i)$ and $(ii),$ ${\gamma }_R(G)=3.$

Proposition 6. (Cockayne et al., 2004) For any graph $G,$ $\gamma (G)\le {\gamma }_R(G)\le 2\gamma (G).$

Theorem 7. Let $G$ be a connected graph of order $n\ge 2.$ Then ${\gamma }_R(G)=n$ if and only if $G\cong P_2.$

Proof. It is clear that ${\gamma }_R(P_2)=2.$

Let ${\gamma }_R(G)=n.$ By Theorem 1 and Proposition 6, $\gamma (G)=\frac{n}{2}.$ Also, by Theorem 2, $G\cong C_4$ or $G\cong H\circ K_1,$ where $H$ is a connected graph. Since ${\gamma }_R(C_4)=3,$ so $G\cong H\circ K_1.$ If $|V(H)|\ge 2,$ then $P_4$ is an induced subgraph of $H\circ K_1.$ We know that ${\gamma }_R(P_4)=3.$ So ${\gamma }_R(H\circ K_1)<2|V(H)|=n,$ which is a contradiction. Hence, $|V(H)|=1$ and so $G\cong P_2.$

Corollary 8. Let $G$ be a graph of order $n.$ Then ${\gamma }_R(G)=n$ if and only if $G\cong {\bigcup }_{i=1}^t{K}_1{\bigcup }_{j=1}^s{P}_2.$

Proof. By Theorem 7, the proof is straightforward.

Lemma 9. Let $G$ be a graph of order $n=1$ and $\sigma :V(G)\to V(G^{\prime })$ be a function. Then ${\gamma }_R(C(G,\sigma ))={\gamma }_R(\overline{C(G,\sigma )})=2.$

Proof. If $n=1,$ then $C(G,\sigma )\cong P_2.$ By Corollary 8, ${\gamma }_R(C(G,\sigma ))={\gamma }_R(\overline{C(G,\sigma )})=2.$

Theorem 10. Let $G$ be a graph of order $n$ and $\sigma :V(G)\to V(G^{\prime })$ be a permutation. Then ${\gamma }_R(G)\le {\gamma }_R(C(G,\sigma ))\le 2{\gamma }_R(G).$

Proof. Let $f=(V_0,V_1,V_2)$ be a $RDF$ for $G.$ We define $g:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as $g=(V_0\cup {V_0}^{\prime },V_1\cup {V_1}^{\prime },V_2\cup {V_2}^{\prime }),$ where ${V_i}^{\prime }$ is corresponding to $V_i$ for $i\in \{0,1,2\}.$ It is easy to see that $g$ is a $RDF$ for $C(G,\sigma )$ and so ${\gamma }_R(C(G,\sigma ))\le \omega (g)=2\omega (f)=2{\gamma }_R(G).$

Now let $f=(W_0,W_1,W_2)$ be a $RDF$ for $C(G,\sigma )$ with ${\gamma }_R(C(G,\sigma ))=\omega (f).$ Also let ${W_0}^{\prime }=W_0\cap V(G),$ ${W_1}^{\prime }=W_1\cap V(G)$ and ${W_2}^{\prime }=W_2\cap V(G).$ We set $W_0^{\ast }=\{x\in {W_0}^{\prime }|N_{G^{\prime }}(x)\cap {W_2}^{\prime }=\mathrm{\varnothing }\}.$ We define $g:V(G^{\prime })\to \{0,1,2\}$ as

$g(x)=\left\{\begin{array}{cc}f(x),& x\in {W_1}^{\prime }\cup {W_2}^{\prime }\\ 1,& x\in W_0^{\ast }\\ 0& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

Then $g$ is a $RDF$ for $G^{\prime }$ and so ${\gamma }_R(G^{\prime })\le \omega (g).$ Since $\omega (g)<\omega (f)={\gamma }_R(C(G,\sigma )),$ so ${\gamma }_R(G)\le {\gamma }_R(C(G,\sigma ))\le 2{\gamma }_R(G).$

Theorem 11. Let $G$ be a graph of order $n$ and $\mathrm{\Delta }(G)=n-1.$ If $\sigma :V(G)\to V(G^{\prime })$ be a function, then

i) $2\le {\gamma }_R(C(G,\sigma ))\le 4.$

ii) ${\gamma }_R(C(G,\sigma ))=2$ if and only if $B_n=\{a\}$ and $a$ be an universal vertex of $G^{\prime }.$

iii) ${\gamma }_R(C(G,\sigma ))=3$ if and only if $B_n=\{a\}$ and $de{g}_{G^{\prime }}(a)=n-2$ or $B_{n-1}=\{a\}$ and $de{g}_{G^{\prime }}(a)=n-1$

Proof. i) Let $a$ be an universal vertex of $G.$ We define $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$f(x)=\left\{\begin{array}{cc}2,& x\in \{a,a^{\prime }\}\\ 0& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

It is clear that $f$ is a $RDF$ for $C(G,\sigma )$ and so ${\gamma }_R(C(G,\sigma ))\le 4.$ By Lemma 5, $2\le {\gamma }_R(C(G,\sigma )).$

ii) Let ${\gamma }_R(C(G,\sigma ))=2.$ By Lemma 5, $\mathrm{\Delta }(C(G,\sigma ))=2n-1.$ So there is an universal vertex $a\in V(G)\cup V(G^{\prime }).$ Hence, $a\in V(G^{\prime })$ and so $B_n=\{a\}.$

Conversely, let $B_n\ne \mathrm{\varnothing }$ and $a$ is an universal vertex of $G^{\prime }.$ We define $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$f(x)=\left\{\begin{array}{cc}2,& x=a\\ 0& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

is a $RDF$ for $C(G,\sigma ).$ Hence, ${\gamma }_R(C(G,\sigma ))\le 2.$ By Lemma 5, ${\gamma }_R(C(G,\sigma ))=2.$

iii) Let ${\gamma }_R(C(G,\sigma ))=3.$ By Lemma 5, there are two elements $a$ and $b$ in $V(G)\cup V(G^{\prime }),$ such that $de{g}_C(a)=2n-2$ and $a\nsim b$ in $C(G,\sigma ).$ By the definition of $C(G,\sigma ),$ $a\in V(G^{\prime }).$ If $b\in V(G^{\prime }),$ then $a\in B_n$ and $de{g}_{G^{\prime }}(a)=n-2.$ If $b\in V(G),$ then $a\in B_{n-1}$ and $de{g}_{G^{\prime }}(a)=n-1.$

Conversely, let $B_n=\{a\},$ $de{g}_{G^{\prime }}(a)=n-2$ and $b\in V(G^{\prime }),$ such thst $b\nsim a$ in $G^{\prime }$ or $B_{n-1}=\{a\},$ $de{g}_{G^{\prime }}(a)=n-1$ and $b\in V(G),$ such that $\sigma (b)\ne a.$ We define $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$f(x)=\left\{\begin{array}{cc}2,& x=a\\ 1,& x=b\\ 0,& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

Then $f$ is a $RDF$ for $C(G,\sigma ).$ Hence, ${\gamma }_R(C(G,\sigma ))\le 3.$ By Lemma 5, ${\gamma }_R(C(G,\sigma ))=3.$

Therefore, the proof is straightforward.

3. Roman domination number of$\overline{C\mathit{(}G\mathit{,}\sigma \mathit{)}}$

In this section, we introduce a bound for Roman domination number of $\overline{C(G,\sigma )}$ and calculate the exact value of Roman domination number of functigraphs of some special graphs.

Theorem 12. For each graph $G,$ $2\le {\gamma }_R(\overline{C(G,\sigma )})\le 5,$ where $\sigma :V(G)\to V(G^{\prime })$ is a function.

Proof. Let $B_1\ne \mathrm{\varnothing },$ $u\in B_1$ and $R_u=\{v\}.$ We define $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}.$ Then

$f(x)=\left\{\begin{array}{cc}2,& x\in \{u,v\}\\ 0,& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

is a $RDF$ for $C(G,\sigma ).$ Hence, ${\gamma }_R(\overline{C(G,\sigma )})\le \omega (f)=4.$

Let $B_1=\mathrm{\varnothing }.$ Then $B_0\ne \mathrm{\varnothing }.$ Suppose that $u\in B_0$ and $v$ is an arbitrary vertex in $V(G).$ Then the function $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$f(x)=\left\{\begin{array}{cc}2,& x\in \{u,v\}\\ 1,& x=\sigma (v)\\ 0& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

is a $RDF$ for $\overline{C(G,\sigma )}.$ Thus ${\gamma }_R(\overline{C(G,\sigma )})\le \omega (f)=5.$ By Lemma 5, we have $2\le {\gamma }_R(\overline{C(G,\sigma )})\le 5.$

Corollary 13. Let $G$ be a graph with $\delta (G)\ge 1$ and $\sigma :V(G)\cup V(G^{\prime })\to \{0,1,2\}$ be a function. Then $3\le {\gamma }_R(\overline{C(G,\sigma )})\le 5.$

Proof. Let ${\gamma }_R(\overline{C(G,\sigma )})=2.$ By Lemma 5, $C(G,\sigma )$ is an universal vertex as $a.$ So $a$ is an isolated vertex in $\overline{C(G,\sigma )}.$ Which is not true.

Theorem 14. Let $G$ be a graph of order $n$ with $\delta (G)\ge 1$ and $\sigma :V(G)\to V(G^{\prime })$ be a function. Then ${\gamma }_R(\overline{C(G,\sigma )})=3$ if and only if $B_0\ne \mathrm{\varnothing },$ $a\in B_0$ and $de{g}_{G_2}(a)=1.$

Proof. Let ${\gamma }_R(\overline{C(G,\sigma )})=3.$ By Lemma 5, there are two elements $a$ and $b$ in $V(G)\cup V(G^{\prime }),$ such that $de{g}_{\bar{C}}(a)=2n-2$ and $a\nsim b$ in $\overline{C(G,\sigma )}.$ So $de{g}_C(a)=1$ and $N_C(a)=\{b\}.$ Since $\delta (G)\ge 1,$ so $\{a,b\}\subseteq V(G^{\prime }).$ Hence, $a\in B_0.$ Therefore $B_0\ne \mathrm{\varnothing },$ $a\in B_0$ and $de{g}_{G^{\prime }}(a)=1.$

Conversely, suppose that $a\in B_0$ and $de{g}_{G^{\prime }}(a)=1.$ Then the function $g:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$g(x)=\left\{\begin{array}{cc}2,& x=a\\ 1,& x=b\\ 0,& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

is a $RDF$ for $\overline{C(G,\sigma )},$ where $a$ is adjacent to $b$ in $G^{\prime }.$ So ${\gamma }_R(\overline{C(G,\sigma )})\le \omega (g)=3.$ By Corollary 13, ${\gamma }_R(\overline{C(G,\sigma )})=3.$

Corollary 15. Let $G$ be a graph of order $n\ge 3$ with $\delta (G)\ge 1$ and $\sigma :V(G)\to V(G^{\prime })$ be a function. If $B_0=\mathrm{\varnothing }$ or for every $a\in B_0,$ $de{g}_{G^{\prime }}(a)\ge 2,$ then ${\gamma }_R(\overline{C(G,\sigma )})\in \{4,5\}.$

Proof. By Theorem 14, the proof is straightforward.

Lemma 16 Let $G$ be a graph and for some $u\in V(G^{\prime }),$ induced subgraph on $N_{G^{\prime }}(u)$ has an isolated vertex and $\sigma :V(G)\to V(G^{\prime })$ be a function. Then ${\gamma }_R(\overline{C(G,\sigma )})\in \{2,3,4\}.$

Proof. Let $u_0\in V(G^{\prime })$ be an isolated vertex of induced subgraph on $N_{G^{\prime }}(u).$ We define $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$g(x)=\left\{\begin{array}{cc}2,& x\in \{u_0,u\}\\ 0,& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

It is easy to see that $f$ is a $RDF$ of $\overline{C(G,\sigma )}.$ Hence, ${\gamma }_R(\overline{C(G,\sigma )})\le \omega (f)=4.$ Therefore, by Lemma 5, $(i),$ we have $2\le {\gamma }_R(\overline{C(G,\sigma )})\le 4.$

Theorem 17. Let $G≆K_4$ be a cubic graph and $\sigma :V(G)\to V(G^{\prime })$ be a function. Then ${\gamma }_R(\overline{C(G,\sigma )})=4.$

Proof. By Corollary 15, ${\gamma }_R(\overline{C(G,\sigma )})\in \{4,5\}.$ Let $u\in V(G^{\prime })$ and $N_{G^{\prime }}(u)=\{u_1,u_2,u_3\}.$ If induced subgraph on $N_{G^{\prime }}(u)$ has an isolated vertex, then by Lemma 16, ${\gamma }_R(\overline{C(G,\sigma )})=4.$

Let induced subgraph on $N_{G^{\prime }}(u)$ does not have any isolated vertex. Since $G≆K_4$so induced subgraph on $N_{G^{\prime }}(u)$ is isomorphic to $P_3.$ Hence, there is an $x\in V(G^{\prime })\mathrm{\setminus }\{u_1,u_2\},$ such that $x$ is adjacent to $u_3$ in $G^{\prime }.$ We see that $x$ is an isolated vertex in induced subgraph on $N_{G^{\prime }}(u_3).$ Therefore, ${\gamma }_R(\overline{C(G,\sigma )})=4.$

Theorem 18. Let $n\ge 4,$ $G\cong K_n$ and $\sigma :V(G)\to V(G^{\prime })$ be a function.Then ${\gamma }_R(\overline{C(G,\sigma )})=4$ if and only if $B_1\ne \mathrm{\varnothing },$ where $\sigma \in S_n.$

Proof. Let ${\gamma }_R(\overline{C(G,\sigma )})=4$ and $B_1=\mathrm{\varnothing }.$ Also, let $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ be a $RDF$ for $\overline{C(G,\sigma )}$ with $\omega (f)=4.$ Then there are two vertices $a$ and $b$ in $V(G)\cup V(G^{\prime })$ or there are three vertices $a,$ $b$ and $c$ in $V(G)\cup V(G^{\prime }),$ such that $f(a)=f(b)=2$ or $f(a)=2$ and $f(b)=f(c)=1,$ respectively. Assume that $f(a)=f(b)=2.$ It is easy to see that $a\in V(G)$ and $b\in V(G^{\prime }).$ We have two following cases.

Case 1: Let $b\in B_0.$ Then $f(\sigma (a))\ne 0.$ This is contradiction to this fact that ${\gamma }_R(\overline{C(G,\sigma )})=4.$

Case 2: Let $b\notin B_0.$ Since $B_1=\mathrm{\varnothing },$ so there are $x$ and $y$ in $V(G),$ such that $\sigma (x)=\sigma (y)=b.$ Hence, $f(x)\ne 0$ and $f(y)\ne 0.$ That is not true.

Now, Let $f(a)=2$ and $f(b)=f(c)=1.$ Then $a\in B_0$ and $N_{G^{\prime }}(a)=\{b,c\}.$ Thus $G\cong K_3.$ That is contradiction.

Conversely, let $B_1\ne \mathrm{\varnothing },$ $b\in B_1$ and $\sigma (a)=b.$ We define function $f:V(G)\cup V(G^{\prime })\to \{0,1,2\}$ as

$f(x)=\left\{\begin{array}{cc}2,& x\in \{a,b\}\\ 0,& \mathrm{o}.\mathrm{w}.\\ \hspace{0.17em}& \hspace{0.17em}\end{array}\right.$

It is easy to see that $f$ is a $RDF$ for $\overline{C(G,\sigma )}.$ So ${\gamma }_R(\overline{C(G,\sigma )})\le \omega (f)=4.$ By Corollary 15, ${\gamma }_R(\overline{C(G,\sigma )})=4.$

Corollary 19. Let $n\ge 3,$ $G\cong K_n$ and $\sigma :V(G)\to V(G^{\prime })$ be a function. Then ${\gamma }_R(\overline{C(G,\sigma )})=5$ if and only if $B_1=\mathrm{\varnothing }.$

Proof. Let $B_1\ne \mathrm{\varnothing }.$ By Theorem 18, ${\gamma }_R(\overline{C(G,\sigma )})=4.$

Conversely, let $B_1=\mathrm{\varnothing }.$ By Theorem 18, ${\gamma }_R(\overline{C(G,\sigma )})\ne 4.$ By Corollary 15, ${\gamma }_R(\overline{C(G,\sigma )})=5.$

Theorem 20. Let $G\cong P_n$ be a graph of order $n\ge 2$ and $\sigma :V(G)\to V(G^{\prime })$ be a function. Then

i) ${\gamma }_R(\overline{C(G,\sigma )}\in \{3,4\}.$

ii) ${\gamma }_R(\overline{C(G,\sigma )}=3$ if and only if $\{v_1,v_2\}\subseteq B_0.$

Proof. i) By Lemma 16, ${\gamma }_R(\overline{C(G,\sigma )}\in \{2,3,4\}.$ By Corollary 13, since $\delta (G)\ge 1,$ so ${\gamma }_R(\overline{C(G,\sigma )}\in \{3,4\}.$

ii) By Theorem 14, the proof is straightforward.

Drear professor,

Thank you very much for your concerning. Here, i supply our biography and interest statements.

Acknowledgements

The authors are very grateful to the referee for his/her useful comments.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

Ebrahim Vatandoost

Ebrahim Vatandoost is presently working as an assistant professor in the Department of Mathematics, Imam Khomeini International University, Qazvin, Iran. His field of specialties includes Group Theory and Graph Theory

Athena Shaminejad is a PhD candidate of graph theory in the Department of Mathematics, Imam Khomeini International University, Qazvin, Iran. Her favorite fields are Graph Theory and Graph Theory.