论文部分内容阅读
P.Kelly于1966年提出如下猜想:
“若D顶点数是n为奇数的竞赛图,并且每个入度和出度都等于(n-1)/2,则D是(n-1)/2条弧不重的有向Hamilton圈的并图。”
这一猜想被Bondy《图论及其应》一书列为50个难解问题之一,至今末获解决。一些学者只是在顶点数为3和5的特殊情形证明了猜想的正确性。
本文用置换群,有限域等代数学方法,对这一问题进行了深入的研究。获得了如下结果。
1.若D是n为奇数的竞赛图,并且每个顶点的入度和出度都等于(n-1)/2。那么,竞赛图D=(V,E)是Hamilton图。
2.竞赛图D有奇数个顶点{v0,v1,…,vn-1},使这奇数个顶点按逆时针方向排列。对任一顶点vi,i=1,2,…,n,使得它的出度顶点集为{vi=1,vi+2,…,vi+(n-1)/2}(modn),入度顶点集为{vi+(n-1)/2+1,vi+(n-1)/2+2,…,vi+(n-1)/2+(n-1)/2}(modn)。
如果竞赛图D的顶点个数n为奇质数,对D的每一个顶点都有d-(v)=d+(v)=(n-1)/2,且D的顶点排列满足上面所述的标准。那么,竞赛图D是一个(n-1)/2条弧不重的Hamilton圈的并图。
3.如果竞赛图D的顶点个数n为奇质数,对D的每一个顶点都有d-(v)=d+(v)=(n-1)/2。那么,存在(n-1)/2条弧不重的Hamilton圈,使得竞赛图D是这(n-1)/2条弧不重的Hamilton圈的并图。