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