Document Type : Research Paper

Authors

1 Department of mathematics, Imam Khomeini International University, P. O. Box 3414896818, Qazvin, Iran

2 Department of mathematics, Imam Khomeini International University, P. O. Box 3414896818, Qazvin, Iran.

Abstract

Let $G=(V, E)$ be a simple graph. A subset $S \subseteq V(G)$ is a \textit{dominating set} of $G$ if every vertex in $V(G) \setminus S$ is adjacent to at least one vertex in $S.$ The \textit{domination number} of graph $G,$ denoted by $\gamma(G),$ is the minimum size of a dominating set of vertices $V(G).$ Let $G_1$ and $G_2$ be two disjoint copies of graph $G$ and $f:V(G_1)\rightarrow V(G_2)$ be a function. Then a \textit{functigraph} $G$ with function $f$ is denoted by $C(G, f),$ its vertices and edges are $V(C(G, f))=V(G_1) \cup V(G_2)$ and $E(C(G, f))=E(G_1) \cup E(G_2) \cup \{vu| v \in V(G_1) , u \in V(G_2), f(v)=u\},$ respectively. In this paper, we investigate domination number of complements of functigraphs. We show that for any connected graph $G,$  $\gamma(\overline{C(G, f)}) \leq 3.$ Also we provide conditions for the function $f$ in some graphs such that $\gamma(\overline{C(G, f)})=3.$ Finally, we prove if $G$ is a bipartite graph or a connected $k-$ regular graph of order $n \geq 4$ for $k \in \{2, 3, 4 \}$ and $G \notin \{K_{3}, K_{4}, K_{5}, H_{1}, H_{2}\},$ then $\gamma(\overline{C(G, f)}) = 2.$

Highlights

The PDF file of this article will be published online after final confirmation by the authors (galley proofs).

Keywords