Some results on anti-duplication graphs

Abstract

For a finite undirected graph $G (V,E)$, anti-duplication of a vertex $v\in V(G)$ produces a new graph $G'$ by adding a new vertex $v'$ such that $N_{G'}(v') = \overline{(N_G(v))}$. In other words a vertex $v'$ is said to be anti-duplication of $v$ if all the vertices which are adjacent to $v$ in $G$ are non-adjacent to $v'$ in $G'$ and the vertices which are non-adjacent to $v$ are adjacent to $v$ in $G'$. In this paper, we introduce a new graph called Anti-duplication graph ADG and study its properties. The anti-duplication graph of $K_p$ and $\bar{K}_p$ are found. We also characterize the anti-duplication graph to be regular and eulerian.