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.

Acknowledgements

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

Drear professor,

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

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.