完全圖的{3，4，8}-圈分解.pdf

1、設Kv為完全圖，F為Kv的一個一因子(當v≡0(mod 2)時)，若(3)mi，3≤mi≤v，I=1，2，．．．，t，滿足條件：Kv(或Kv-F)=C1+C2+…+Gt，其中Gi的長度為mi，則稱Kv(或Kv-F)可以被mi長圈分解．
　　 顯然，完全圖可以被mi長圈分解的必要條件為：
　　 (I)3≤mi≤v，I=1，2，．．．，t；
　　 (ii)m1+m2+…+mt=v(v-1)/2(v≡1(mod 2))

2、；
　　 m1+m2+…+mt=v(v-2)/2(v≡0(mod 2))．
　　 關于這個必要條件是否也充分的問題由Alspach在1981[1]年提出．因此，被稱為Alspach猜想．
　　 這是一個非常大的猜想，要完全證明這個猜想是很困難的．自Alspach提出這個猜想以來，已證明成立的只有以下幾種情況：
　　 (1)v≤14；
　　 (2)m1=m2=…=mt；
　　 (3)mi∈A

3、，I=1，2，…，t．A∈{{3，4，5}，{3，4，6}，{4，6，8}，{4，10}，{6，10}，{8，10}，{3，v}，{u-2，v-1，v}}∪{{2k，2k+1}｜k≥2}．
　　 本文主要是通過對前人證明方法的綜合應用，證明當mi∈{3，4，8}時猜想成立．因為有3長圈，3為奇數，而完全二部圖是不可能出現奇長圈的，這就使得在構造過程中遇到了困難，所以這里我們應用了一些技巧和方法．
　　 本文第二章第一部分

4、證明了當v≡0(mod 2)時本文的結論成立．首先給出了將會用到的引理，然后主要運用了若存在相應的GDD，PBD，則它們可將Kn-F分解為若干個小階數的子圖，再通過討論解的情況將這些小階數子圖分解，就可得到結論．并不是所有情形都可以順利的用一種GDD或PBD來解決，在這時候，就要根據實際情況再用另外的GDD來重新對Kv-F進行分解，討論．此外還有一些小階數的沒有相應的GDD，就要另外再用其他方法來解決這個問題，比如特殊情況下的具體構造．

5、第二部分是對于v≡(mod 2)時情況的證明．在證明時首先運用了在mi∈{4，6，8}證明過程中用到的方法，即構造路圖，拆圖重組．本節(jié)一開始就給出了v≡1(mod 2)時要用的重要引理，即若Kv-4的{3，4，8}-分解已經得到，則Kv的{3，4，8}-圈分解中，C8的個數z≥(v-1)/2時就可以得到，再通過把Kv表示成幾個圖的并的方法來解決C8的個數z<(v-1)/2的情況．這樣，v≡1(mod 2)時的情況就都得到了．