Opuscula Mathematica (Oct 2020)

On 2-rainbow domination number of functigraph and its complement

  • Athena Shaminezhad,
  • Ebrahim Vatandoost

DOI
https://doi.org/10.7494/OpMath.2020.40.5.617
Journal volume & issue
Vol. 40, no. 5
pp. 617 – 627

Abstract

Read online

Let \(G\) be a graph and \(f:V (G)\rightarrow P(\{1,2\})\) be a function where for every vertex \(v\in V(G)\), with \(f(v)=\emptyset\) we have \(\bigcup_{u\in N_{G}(v)} f(u)=\{1,2\}\). Then \(f\) is a \(2\)-rainbow dominating function or a \(2RDF\) of \(G\). The weight of \(f\) is \(\omega(f)=\sum_{v\in V(G)} |f(v)|\). The minimum weight of all \(2\)-rainbow dominating functions is \(2\)-rainbow domination number of \(G\), denoted by \(\gamma_{r2}(G)\). Let \(G_1\) and \(G_2\) be two copies of a graph G with disjoint vertex sets \(V(G_1)\) and \(V(G_2)\), and let \(\sigma\) be a function from \(V(G_1)\) to \(V(G_2)\). We define the functigraph \(C(G,\sigma)\) to be the graph that has the vertex set \(V(C(G,\sigma)) = V(G_1)\cup V(G_2)\), and the edge set \(E(C(G,\sigma)) = E(G_1)\cup E(G_2 \cup \{uv ; u\in V(G_1), v\in V(G_2), v =\sigma(u)\}\). In this paper, \(2\)-rainbow domination number of the functigraph of \(C(G,\sigma)\) and its complement are investigated. We obtain a general bound for \(\gamma_{r2}(C(G,\sigma))\) and we show that this bound is sharp.

Keywords