Domination number of complements of functigraphs

Subject Areas : Combinatorics, Graph theory

A. Shaminejad ¹ , E. Vatandoost ²

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.

Received: 2020-10-29 Accepted : 2021-03-25 Published : 2021-03-01

Keywords: Domination, Domination Number, functigraph,

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.$

References:

[1] J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami, L. Volkmann, Total roman domination number of trees, Australasian. J. Combinatorics. 69 (2) (2017), 271-285.

[2] L. Eroh, R. Gera, C. X. Kang, C. Larson, E. Yi, Domination in functigraphs, Discuss. Math. Graph. Theory. 32 (2) (2012), 299-319.

[3] F. Ramezani, E. D. Rodriguez-Bazan, J. A. Rodriguez-Velazquez, On the roman domination number of generalized Sierpinski graphs, Filomat. 31 (20) (2017), 6515-6528.

[4] E. Vatandoost, F. Ramezani, On the domination and signed domination numbers of zero-divisor graph, Electronic. J. Graph. Theory. Appl. 4 (2) (2016), 148-156.