Let V(G) and E(G) denote the vertex set and the edge set of a graph G; let Kn denote the complete graph with n vertices and let Kn, m denote the complete bipartite graph on n and m vertices. A Hamiltonian cycle (Hamiltonian path, respectively) in a graph G is a cycle (path, respectively) in G that contains all the vertices of G.