一类完全多部图的Hamiton性刻画

Hamiltonian Character of a Class of Completen-partite Graph

Gutin证明了在强的半完全二部图中若含有一个由两个圈构成的圈因子,则图是Hamilton图。把此定理推广到无向图中就可得到这样一个结果,即含有一个由两个圈构成的圈因子的完全二部图是Hamilton图。在此基础上,对含有由两个圈构成的圈因子的完全n(n≥3)部图进行了讨论,得出了类似于二部图的结果。

Gutin have proved that a strong semicomplete bipartite digraph is hamiltonian if it contains a cycle factor consisting of two cycles, which can be extended in undirected graph. In this paper, we discuss complete n-partite graphs containing a cycle factor consisting of two cycles and obtain similar results to the complete bipartite graphs.