## DIMACS TR: 2001-13

## On Hamiltonian Cycles in Strong Products of Graphs

### Authors: Daniel Kral, Jana Maxova, Pavel Podbrdsky, Robert Samal

**
ABSTRACT
**

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