We prove that the strong product $G_1\times\cdots\times G_n$ contains a hamiltonian cycle for $n\ge\Delta$ whenever all $G_i$ are connected graphs of maximum degree at most $\Delta$; in particular $G^{\Delta(G)}$ contains a hamiltonian cycle. For large $\Delta$ we prove the same statement for $n\approx c\Delta$ for any $c>\ln (25/12) +1/60$.
The research was done as a part of Research Experience for Undergraduates
programme; this is a joint programme of DIMACS at Rutgers University and
DIMATIA at Charles University.
The REU supervisors were J\'anos Koml\'os and Endre Szemer\'edi from Rutgers
and Jan Kratochv\'{\i}l and Jaroslav Ne\v{s}et\v{r}il from Charles University.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-13.ps.gz
DIMACS Home Page