Hamiltonicity of Cartesian products of graphs

Abstract

A path factor in a graph $G$ is a factor of $G$ in which every component is a path on at least two vertices. Let $T\square P_n$ be the Cartesian product of a tree $T$ and a path on $n$ vertices. Kao and Weng proved that $T\square P_n$ is hamiltonian if $T$ has a path factor, $n$ is an even integer and $n\ge 4\Delta (T)-2$. They conjectured that for every $\Delta \ge 3$ there exists a graph $G$ of maximum degree $\Delta$ which has a path factor, such that for every even $n<4\Delta -2$ the product $G\square P_n$ is not hamiltonian. In this article we prove this conjecture.