On roman domination number of functigraph and its complement
Ebrahim Vatandoost, Athena Shaminezhad · Cogent Mathematics & Statistics · 2020
Let G=(V(G),E(G)) be a graph and f:V(G)→{0,1,2} be a function where for every vertex v∈V(G) with f(v)=0, there is a vertex u∈NG(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))=∑v∈V(G)f(v). The minimum weight of all RDF is called the Roman domination number of G, denoted by γR(G). Let G be a graph with V(G)={v1,v2,…,vn} and G' be a copy of G with V(G′)={v1′,v2′,…,vn′}. Then a functigraph G with function σ:V(G)→V(G′) is denoted by C(G,σ), its vertices and edges are V(C(G,σ))=V(G)∪V(G′) and E(C(G,σ))=E(G)∪E(G′)∪{v∼v′|v∈V(G),v′∈V(G′),σ(v)=v′}, respectively. This paper deals with the Roman domination number of the functigraph and its complement. We present a general bound γR(G)≤γR(C(G,σ))≤2γR(G), where σ:V(G)→V(G′) is a permutation. Also, the Roman domination number of some special graphs are considered. We obtain a general bound of γR(C(G,σ)‾ and we show that this bound is sharp.