Premium
Hamiltonian cycles in k ‐partite graphs
Author(s) -
DeBiasio Louis,
Krueger Robert A.,
Pritikin Dan,
Thompson Eli
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22508
Subject(s) - hamiltonian path , mathematics , combinatorics , hamiltonian (control theory) , discrete mathematics , graph , pancyclic graph , hamiltonian path problem , line graph , pathwidth , mathematical optimization
Chen et al 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 that all parts have at most n / 2 vertices (a necessary condition). To do this, we first prove a general result that 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.