關于Hamilton-Waterloo問題的研究.pdf

1、組合設計理論是離散數(shù)學的一個重要分支，這一理論的基本問題即是各類設計的存在性與構作，自1847年Kirkman[64，108]解決一類經(jīng)典的設計即Steiner三元系的存在性問題以來，關于組合設計的研究得到了蓬勃的發(fā)展.近幾十年來可分解設計尤其得到重視，歷史上著名的Kirkman女生問題即是研究λ=1時的可分解三元系（即Kirkman三元系）的存在性，這一問題歷經(jīng)一百多年，已經(jīng)由Ray-Chadhuri與Wilson[86]和陸家羲[7

2、9]分別獨立地予以解決.
　　區(qū)組設計的存在性問題可以看作圖分解為完全子圖的問題.如Steiner三元系即為完全圖的3階完全圖分解.在區(qū)組設計之后，圈設計自然地成為了圖的分解問題的一個重要的研究對象.關于這一問題的研究最早可以追溯到20世紀60年代，Kotzig[67]和Rosa[90]解決了完全圖K2xk+1的七-圈分解問題.從那以后，圈分解問題尤其是完全圖的可分解的圈分解問題引起了很多專家學者的關注.關于這一問題已有數(shù)百篇文章

3、發(fā)表.
　　在完全圖的圈分解問題中，Oberwolfach問題是其中重要的一類.這一問題是Ringle于1967年在德國Oberwolfach召開的圖論會議上提出的，它研究的是是否可以把完全圖分解成一些2-因子（2-正則生成子圖），使得所有的2-因子都同構于一個給定的2-因子F.當F由長為3的圈組成時，此問題即是Kirkman女生問題，而當F為一個Hamilton圈時，這一問題就是完全圖的Hamilton圈分解問題.
　　H

4、amilton-Waterloo問題是Oberwolfach問題的一個推廣.對于給定的2-因子R和S，Hamilton-Waterloo問題研究是否能把完全圖Kn（當n為奇數(shù)時）或Kn-In（當n為偶數(shù)時，In為Kn的一個1-因子）分解為若干個2-因子，使得其中r個2-因子同構于R，另外s個同構于S.當給定的兩個2-因子分別由長為p和q的圈組成時，我們稱這樣的2-因子分解是均勻的，此時記2-因子分解為HW(n;r，s;p，q).本文將對

5、均勻情形的Hamilton-Waterloo問題展開研究，重點研究其中一類2-因子為Hamilton圈，另一類2-因子由k長圈構成（記為Ck-因子）的情形，其中k為任意給定正整數(shù).
　　本文第一章將詳細介紹Hamilton-Waterloo問題的歷史，研究進展，研究方法及本文的主要結果.
　　在第二章中我們首先給出HW(n;r，s;p，q)存在的必要條件.然后分奇數(shù)階完全圖和偶數(shù)階完全圖兩種情況，對HW(n;r，s;n，2k

6、+1)的存在性展開研究，證明了當Hamilton圈的個數(shù)大于一個依賴于n和k的數(shù)時，相應的2-因子分解是存在的.
　　第三章對n為偶數(shù)時HW(n;r，s;n，3)的存在性進行深入的研究.當n=0(mod18)時，我們利用擬Kirkman三元系的相關結果，除了3個情形外，證明了對于任意滿足第二章給出的必要條件的n，HW(n;r，s;n，3)均是存在的.當n三6(mod18)時，我們利用Kirkman3-標架設計的結果，除了r=1的情