Hamiltonian Cycles in Strong Products of Graphs

Abstract

Abstract. Let denote the graph (k times) where is the strong product of the two graphs G and H . In this paper we prove the conjecture of J. Zaks [3]: For every connected graph G with at least two vertices there exists an integer k = k ( G ) for which the graph is hamiltonian.