The Existence of Hamilton Cycle in n-Balanced k-Partite Graphs

Abstract

Let $G_{k,n}$ be the $n$-balanced $k$-partite graph, whose vertex set can be partitioned into $k$ parts, each has $n$ vertices. In this paper, we prove that if $k\ge 2,n\ge 1$, for the edge set $E(G)$ of $G_{k,n}$ $$|E(G)|\ge \{\begin{array}{ccc}1& \text{ if }k=2,n=1n^2{C}_k^2-(k-1)n+2& \text{ other }\end{array}$$ then $G_{k,n}$ is hamiltonian. And the result may be the best.