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 \not\in \{2K_2, K_2\}\).