Domination in Some Image Graphs

Abstract

Let $G$ = $(V,E)$ be a simple connected and undirected graph. A subset $D$ of $V$ is called a dominating set of $G$ if every vertex not in $D$ is adjacent to some vertex in $D$. The domination number of $G$ denoted by $\gamma(G)$ is the minimal cardinality taken over all dominating sets of $G$. The shadow graph of $G$, denoted $D_2(G)$ is the graph constructed from $G$ by taking two copies of $G$, say $G$ itself and $G^{'}$ and joining each vertex $u$ in $G$ to the neighbors of the corresponding vertex $u^{'}$ in $G^{'}$. Let $D$ be the set of all distinct pairs of vertices in $G$ and let $D_{s}$ (called the distance set) be a subset of $D$. The distance graph of $G$, denoted by $D(G, D_{s})$ is the graph having the same vertex set as that of $G$ and two vertices $u$ and $v$ are adjacent in $D(G, D_{s})$ whenever $d(u,v)\in D_{s} $. The image graph of a connected graph $G$, denoted by $I_{mg}(G)$ is the graph obtained by joining the vertices of the original graph $G$ to the corresponding vertices of a copy of $G$. In this paper, we determine the domination number of the image graph of path graph and cycle graph. We also determine the domination number of the shadow distance graph of the image graph of path graph and cycle graph with specified distance sets.