Article ID Journal Published Year Pages File Type
4649370 Discrete Mathematics 2009 7 Pages PDF
Abstract

The cartesian product of a graph GG with K2K2 is called a prism over GG. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph GG to the cartesian product of GG 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 GG and HH be two connected graphs. Let both GG and HH have a 2-factor. If Δ(G)≤g′(H)Δ(G)≤g′(H) and Δ(H)≤g′(G)Δ(H)≤g′(G) (we denote by g′(F)g′(F) the length of a shortest cycle in a 2-factor of a graph FF taken over all 2-factorization of FF), then G□HG□H is hamiltonian.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,