On 2-rainbow domination number of functigraph and its complement

Opuscula Mathematica

article

Athena Shaminezhad¹  Ebrahim Vatandoost (corresponding author)¹ 

[1] Imam Khomeini International University, Department of Basic Science

关键词: 2-rainbow domination number;    functigraph;    complement;    cubic graph.;   

DOI  :  10.7494/OpMath.2020.40.5.617

学科分类：环境科学（综合）

来源: AGH University of Science and Technology Press

【 摘 要 】

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.

【 授权许可】

CC BY-NC