论文部分内容阅读
设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));
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,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为奇数,而完全二部图是不可能出现奇长圈的,这就使得在构造过程中遇到了困难,所以这里我们应用了一些技巧和方法.
本文第二章第一部分证明了当v≡0(mod 2)时本文的结论成立.首先给出了将会用到的引理,然后主要运用了若存在相应的GDD,PBD,则它们可将Kn-F分解为若干个小阶数的子图,再通过讨论解的情况将这些小阶数子图分解,就可得到结论.并不是所有情形都可以顺利的用一种GDD或PBD来解决,在这时候,就要根据实际情况再用另外的GDD来重新对Kv-F进行分解,讨论.此外还有一些小阶数的没有相应的GDD,就要另外再用其他方法来解决这个问题,比如特殊情况下的具体构造.第二部分是对于v≡(mod 2)时情况的证明.在证明时首先运用了在mi∈{4,6,8}证明过程中用到的方法,即构造路图,拆图重组.本节一开始就给出了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)时的情况就都得到了.
第三章的内容是把第二章简单概括,从而得到本文的重要定理:
定理当mi∈{3,4,8}时,Alspach猜想成立(即Kv(或Kv-F)的{3,4,8}-圈分解存在).