On Hamiltonian cycles in balanced k-partite graphs

2019/07/03 by DeBiasio, Louis, Spanier, Nicholas
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.02004

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 \lceil(n)/(2)\rceil+\lfloor(n+2)/(2\lceil(k+1)/(2)\rceil)\rfloor-(n)/(k)=\begincases \lceil(n)/(2)\rceil+\lfloor(n+2)/(k+1)\rfloor-(n)/(k) amp; : k odd
(n)/(2)+\lfloor(n+2)/(k+2)\rfloor-(n)/(k) amp; : k even \endcases, then G has a Hamiltonian cycle unless k=2 and 4 divides n, or k=(n)/(2) and 4 divides n. In the case where k=2 and 4 divides n, or k=(n)/(2) and 4 divides n, we can characterize the graphs which do not have a Hamiltonian cycle and see that \lceil(n)/(2)\rceil+\lfloor(n+2)/(2\lceil(k+1)/(2)\rceil)\rfloor-(n)/(k)+1 suffices. This result is tight for all k≥ 2 and n≥ 3 divisible by k.

Related

• The Existence of Hamilton Cycle in n-Balanced k-Partite Graphs
• Hamiltonian cycles in k-partite graphs
• On the Minimum Number of Hamiltonian Cycles in Regular Graphs
• Hamiltonian paths and cycles in some 4-uniform hypergraphs
• The Hamiltonian Cycle in K_1,r-free Split Graphs -- A Dichotomy