特定的競(jìng)賽圖是弧不同的Hamilton圈的并圖.pdf

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

2、且每個(gè)頂點(diǎn)的入度和出度都等于(n-1)/2。那么，競(jìng)賽圖D=(V，E)是Hamilton圖?！　?.競(jìng)賽圖D有奇數(shù)個(gè)頂點(diǎn){v0，v1，…，vn-1}，使這奇數(shù)個(gè)頂點(diǎn)按逆時(shí)針?lè)较蚺帕?。?duì)任一頂點(diǎn)vi,i=1,2，…，n，使得它的出度頂點(diǎn)集為{vi=1，vi+2，…，vi+(n-1)/2}(modn)，入度頂點(diǎn)集為{vi+(n-1)/2+1，vi+(n-1)/2+2，…，vi+(n-1)/2+(n-1)/2}(modn)?！　∪绻?jìng)賽圖