每条弧都在Hamilton-路上的半完全多部有向图

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (11): 41-42.

每条弧都在Hamilton-路上的半完全多部有向图

孟巍李胜家

山西大学数学科学学院

收稿日期:2006-05-17 修回日期:1900-01-01 出版日期:2007-04-11 发布日期:2007-04-11
通讯作者: 孟巍

Semicomplete Multipartite Digraphs whose every Arc is Contained in a Hamiltonian Path

Received:2006-05-17 Revised:1900-01-01 Online:2007-04-11 Published:2007-04-11

摘要/Abstract

摘要： 用一条弧或一对方向相反的弧代替完全多部无向图的每一条边所得到的有向图被称为是半完全多部有向图。2002年L. Volkmann [6]提出这样一个问题：给出半完全多部有向图中每一条弧都在Hamilton-路上的充分条件。本文将针对此问题给出一个新的充分条件，并举例说明该充分条件的独立性以及它在某种意义下的最佳可能性。

关键词: 半完全多部有向图, Hamilton-路, 半部完全有向图

Abstract: A semicomplete multipartite digraph is obtained by replacing each edge of a complete multipartite graph by an arc or by a pair of two mutually opposite arcs. In 2002, L.Volkmann [6] raised a problem: Determine other sufficient conditions for emicomplete multipartite digraphs such that every arc is contained in a Hamiltonian path. In this paper, we give a new sufficient condition and describe some semicomplete multipartite digraphs demonstrating that this sufficient condition is independent and in some sense, it is best posssible.

Key words: semicomplete multipartite digraphs, Hamilton-path, semi-partition complete digraphs

孟巍李胜家. 每条弧都在Hamilton-路上的半完全多部有向图[J]. 计算机工程与应用, 2007, 43(11): 41-42.