特定的競賽圖是弧不同的Hamilton圈的并圖.pdf

1、P.Kelly于1966年提出如下猜想：　　“若D頂點數(shù)是n為奇數(shù)的競賽圖，并且每個入度和出度都等于(n-1)/2，則D是(n-1)/2條弧不重的有向Hamilton圈的并圖?！薄　∵@一猜想被Bondy《圖論及其應(yīng)》一書列為50個難解問題之一，至今末獲解決。一些學(xué)者只是在頂點數(shù)為3和5的特殊情形證明了猜想的正確性?！　”疚挠弥脫Q群，有限域等代數(shù)學(xué)方法，對這一問題進(jìn)行了深入的研究。獲得了如下結(jié)果?！　?.若D是n為奇數(shù)的競賽圖，并

2、且每個頂點的入度和出度都等于(n-1)/2。那么，競賽圖D=(V，E)是Hamilton圖?！　?.競賽圖D有奇數(shù)個頂點{v0，v1，…，vn-1}，使這奇數(shù)個頂點按逆時針方向排列。對任一頂點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)。　　如果競賽圖