Cycles in complementary prisms

The complementary prism GG¯ of a graph GG arises from the disjoint union of GG and the complement G¯ of GG by adding a perfect matching joining corresponding pairs of vertices in GG and G¯. Partially answering a question posed by Haynes et al. (2007) we provide an efficient characterization of the circumference of the complementary prism TT¯ of a tree TT and show that TT¯ has cycles of all lengths between 3 and its circumference. Furthermore, we prove that for a given graph of bounded maximum degree it can be decided in polynomial time whether its complementary prism is Hamiltonian.