Hamiltonicity and pancyclicity of cartesian products of graphs

AbstractThe cartesian product of a graph G with K2 is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g′(H) and Δ(H)≤g′(G) (we denote by g′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian