On Hamiltonian cycles in balanced k-partite graphs

Abstract For all integers k with k ≥ 2 , if G is a balanced k-partite graph on n ≥ 3 vertices with minimum degree at least ⌈ n 2 ⌉ + ⌊ n + 2 2 ⌈ k + 1 2 ⌉ ⌋ − n k = { ⌈ n 2 ⌉ + ⌊ n + 2 k + 1 ⌋ − n k : k  odd  n 2 + ⌊ n + 2 k + 2 ⌋ − n k : k  even  , then G has a Hamiltonian cycle unless 4 divides n and k ∈ { 2 , n 2 } . In the case where 4 divides n and k ∈ { 2 , n 2 } , we can characterize the graphs which do not have a Hamiltonian cycle and see that ⌈ n 2 ⌉ + ⌊ n + 2 2 ⌈ k + 1 2 ⌉ ⌋ − n k + 1 suffices. This result is tight for all k ≥ 2 and n ≥ 3 divisible by k.