Hamiltonian cycles in k-partite graphs

2017/07/24 by DeBiasio, Louis, Krueger, Robert A., Pritikin, Dan +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1707.07633

Abstract

Chen, Faudree, Gould, Jacobson, and Lesniak determined the minimum degree threshold for which a balanced k-partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary k-partite graphs in which all parts have at most n/2 vertices (a necessary condition). To do this, we first prove a general result which both simplifies the process of checking whether a graph G is a robust expander and gives useful structural information in the case when G is not a robust expander. Then we use this result to prove that any k-partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.

Related

• On Hamiltonian cycles in balanced k-partite graphs
• The Existence of Hamilton Cycle in n-Balanced k-Partite Graphs
• Few hamiltonian cycles in graphs with one or two vertex degrees
• On the Minimum Number of Hamiltonian Cycles in Regular Graphs
• Many Hamiltonian subsets in large graphs with given density