Hamiltonicity of Transformation Graph $G^{+--}$

Abstract

The transformation graph $G^{+--}$ of a graph $G$ is the graph with vertex set $V(G)\cup E(G)$, in which two vertices $u$ and $uv$ are joined by an edge if one of the following conditions holds: (i) $u,v\in V(G)$ and they are adjacent in $G$, (ii) $u,v\in E(G)$ and they are not adjacent in $G$, (iii) one of $u$ and $wv$ is in $V(G)$ while the other is in $E(G)$, and they are not incident in $G$. In this paper, for any graph $G$, we determine the independence number and the connectivity of $G^{+--}$. Furthermore, we show that for a graph $G$ with no isolated vertices, $G^{+--}$ is hamiltonian if and only if $G$ is not a star and $G\notin \{2K_2,K_2\}$.