K_p和K_(p+1)的具有最多Hamilton圈的定向图  

The Most Hamilton Cycles Orientations of K_p and K_(p+1)

作　　者：魏慧敏[1] 

机构地区：[1]大同大学

出　　处：《哈尔滨师范大学自然科学学报》2014年第4期26-28,共3页Natural Science Journal of Harbin Normal University

摘　　要：在文献[3]中,Hoffman等人证明了完全图Kn中最多边不交的Hamilton圈个数为[n-1/2].这说明Kn存在一个定向Tn,使得Tn具有[n-1/2]个弧不相交的Hamilton圈.给出了当n=p和p+1(其中p是一个奇素数)时,一种构造Tn的方法,使用这种方法,可以直接写出Tn的所有弧不相交的Hamilton圈.In paper [ 3 ], Hoffman et al. proved that the number of the most edge - disjoint Homilton cycles is [n-1/2] in the complete graph Kn. This showed that there exists an orientation Tn in Ka such that Tnhas [n-1/2] arc - disjoint Homilton cycles. In this paper, a method of constructing Tn when n = p and p ＋1 is obtained, where p is an odd prime. And all arc - disjoint Homihon cycles of Tn are represented directly using this method.

关 键 词：完全图 定向 弧不相交的Hamilton圈 

分 类 号：O157.5[理学—数学]