关于完全多部图Kn(t)的{C3,Cj,C2k}-强制分解

开篇：润墨网以专业的文秘视角，为您筛选了一篇关于完全多部图Kn(t)的{C3,Cj,C2k}-强制分解范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：关于完全多部图kn(t)的{c3,cj,c2k}-强制分解，是指将Kn(t)分解为长为3或和的圈。本文证明了完全多部图Kn(t)的{C3,C5,C6}-强制分解存在的必要条件也是充分的。

关键词;完全多部图；强制分解；分解

1 引言

用Kn(t)表示以X=∪Xi(i=1,2,…,n)为顶点集的完全n部图，其中Xi(i=1,2,…,n)是n个两两不相交的t元集，其中顶点a∈Xi及b∈Xj在Kn(t)中相邻当且仅当i≠j。符号Ck表示长为k的圈，记为(a1,a2,…,ak)。给定图G，B是图G的一族互不同构的子图，若B中子图的边集形成E(G)的一个划分且每个子图与某一图Fj（1≤j≤r）同构，则称B是图G的一个{F1,F2,…,Fr}-分解。若对任意Fi(i=1,2,…,r)，B中至少有一个子图与Fi同构，则称B为G的一个{F1,F2,…,Fr}-强制分解。本文将给出Kn(t)的{C3,C5,C6}-强制分解的存在的充要条件。

定理Kn(t)的{C3,C5,C6}-强制分解存在的充要条件为：

（1）当t=1时，n≥9且n1(mod2)；（2）当t=2k+1时,n也为大于等于3的奇数；

（3）当t=2k为偶数时，n≥3且(n,t)≠(3,2)。k=1,2,3….

2基本引理

引理1 如果Km(2)的{C3，C5}-强制分解存在，则K2m+1的{C3,C5 }-分解存在。

引理2 n≥4,K={4,5,6,7,8,9,10,11,12,14,15,18,19,23},则Kn(t)存在{ Km(t):m∈K}-分解。

引理3 如果Kn(t)的Ck-分解存在，则对任意的正整数m，Kn(mt)的Ck-分解存在。

引理4 对任意大于1的奇数n,Kn(t)的{K3(t),K5(t)} -分解存在。

引理5 t>1为奇数时，Kn(t)\Kn(1t)的Kn(3)\Kn(1t),Kn(5)\Kn(15)-分解存在。

3定理的证明

必要性：若Kn(t)的{C3,C5,C6}-强制分解存在。因圈Ck的顶点u的度数为2，要使Kn(t)强制分解成某些特定圈，必有Kn(t)的每个顶点度数都为偶数，且对任意u∈Kn(t),d(u)=(n-1)t，故(n-1)t0(mod2)，或当t为奇数时,n也必须为奇数.因为二部图不包含奇圈,所以又有n≥3。由Kn(t)的边数知存在p,q,r∈N。使得n(n-1)t2=2(3p+5q+6r),通过简单计算可证明,其中当(n,t)=(3,2)和3≤n≤7时,Kn(t)的{C3,C5,C6}-强制分解不存在，得证。

充分性：情形1:t=1时，n≥9且n1(mod2)当时；

(i)当1≤n≤7时,Kn显然不存在{C3,C5,C6}-强制分解。

(ii)当n≥9时,显然K(n-1)/2(2)的{C3,C5,C6}-强制分解存在。在K(n-1)/2(2)中再添加一个新顶点，且该新增顶点分别与大小为2的(n-1)/2个顶点类构作C3,这样可得到(n-1)/2个C3,所以Kn的{C3,C5,C6}-强制分解存在。综上，t=1时，n≥9且n1(mod2)时，Kn的{C3,C5,C6}-强制分解存在。

情形2:t=2k+1时，n也为大于1的奇数，k∈N*；

由引理4,要证明Kn(t)存在强制分解,只需证K3(t)和K5(t)的{C3,C5,C6}-强制分解存在。

1.K3(t)的{C3,C5,C6}-强制分解的情形

(i)t=3时,记完全K3(3)的顶点集为{1,4,7}∪{2,5,8}∪{3,6,9}，则可如下构作其{C3,C5,C6}-强制分解:(1,2,3),(8,1,6),(1,5,3,7,9),(2,7,5,9,4),(8,4,6,2,9),(3,4,5,6,7,8).

(ii)t=5时,可先证明K3(3)\K3(1)的{C3,C5,C6}-强制分解存在.这里以{a,4,7}∪{b,5,8}∪{c,6,9}记K3(3)\K3(1)的顶点,其中K3(1)的顶点为{a,b,c},因此,K3(3)\K3(1)的{C3,C5,C6}-强制分解可如下得到：(8,a,6),(a,5,c,7,9),(b,7,5,9,4),(8,4,6,b,9),(c,4,5,6,7,8),又因为K3(5)可分解为K3(3),K3(2),K3(3)\{K3(3),K3(2)},由前面的分析可知K3(5)存在{C3,C5,C6}-强制分解。

(iii)当t>5时,设K3(t)的第i个顶点类为{ai1,ai2,…ait},其中i=1,2,3，记3×t阶矩阵A=(aij)为由K3(t)的顶点构作的矩阵,则我们可如下构作K3(t)的强制分解：

首先取A的前列,构作K3(t-2),由(ii)可知,K3(t-2)存在{C3,C5,C6}-强制分解。其次,取A的最后2列,构作K3(2),显然K3(2)存在{C3,C5,C6}-强制分解。再以最后两行与第一行构作K3(3)\K3(1),由(i)可知,K3(3)\K3(1)存在{C3,C5,C6}-强制分解。最后,对任意s(2≤s≤t-3),分别以第t-1行和t行与s行构作C6,由上分析可知,K3(t)当t>5时,存在{C3,C5,C6}-强制分解。

2.K5(t)的{C3,C5,C6}-强制分解

先看K5(t)\K5(1t)的情形.由引理5,K5(t)\K5(1t)的{K5(3)\K5(13)\K5(5)\K5(15)}-分解存在。

(i)显然K5(3)\K5(13)可分解为10个C6；

(ii)K5(5)\K5(1)的{C3,C5}-强制分解，K5(5)\K5(1)存在{C3,C5}-强制分解。

由(i),(ii),在t>1且为奇数之时,K5(t)\K5(1t)的{C3,C5,C6}-强制分解存在；而K5显然存在C5分解.因此可知K5(t)存在{C3,C5,C6}-强制分解。

情形3:t=2k为偶数时,n≥3且(n,t)≠(3,2);

(i)n=3时,t≥4且为偶数时,易知K3(4)的{C3,C5,C6}-强制分解存在。

假设其中t=2m,m≥2,且m为奇数时,由情形2,K3(m)的{C3,C5,C6}-强制分解存在,由引理1,K3(t)的{C3,C5,C6}-强制分解也存在.若m为偶数,知K3(4)的{C3,C5,C6}-强制分解存在,从而由引理1,易知K3(t)的{C3,C5,C6}-强制分解存在.故当其中的t≥4的偶数时,K3(t)的{C3,C5,C6}-强制分解存在.

(ii)n≥4,且t为偶数时.首先证明Kn(2)的{C3,C5,C6}-强制分解存在；当n≥4时,由引理2，只需证明Kn(2)(n∈{4,5,6,7,8,9,

10,11,12,13,14,15,18,19,23})的{C3,C5,C6}-强制分解情况.

当n=4，5，6，7，8时，Kn(2)显然存在{C3，C5，C6}-强制分解。

当n=9时，我们知道,完全多部图K4(2)的{C3，C5，C6}-强制分解存在，则由引理1，K9的{C3，C5，C6}-强制分解也存在,由引理3知，K9(2)的{C3，C5，C6}-强制分解存在.

当n为{11,15,19,23}之一时，因为K5(2)，K7(2)，K9(2)的{C3，C5，C6}-强制分解都存在。所以当n=9时，由引理1，3，知Kn(2)的{C3，C5，C6}-强制分解存在。当n为{10，12，14，18}中之一时，因Kn(2)存在{Km(2):m∈{3,4,5,6,8}}-分解,且{10,12,14,18}∩{n|n=1，3(mod6)}=Φ,由引理1，在Kn(2)的{Km(2):m∈{3,4,5,6,8}}-分解中存在异于K3(2)的子图,且该子图∈{K4(2)K5(2)K6(2)K8(2)}。由上可知这类子图都存在{C3,C5,C6}-强制分解,所以要使Kn(2)存在{C3,C5,C6}-强制分解,只需分析K3(2)的强制分解情形即可.又由于K3(2)存在C3分解，所以Kn(2)的{C3,C5,C6}-强制分解存在。

综上，在n∈{4，5，6，7，8，9，10，11，12，14，15，18，19，23}时，Kn(2)的{C3,C5,C6}-强制分解存在.当n≥4时，Kn(2)的{C3,C5,C6}-强制分解存。由上可得，当t=2k时，n≥3且(n,t)≠(3,2)时，Kn(t)的{C3，C5，C6}-强制分解存在。

参考文献:

[1]孙惠泉.图论及其应用[M].北京：科学出版社,2004.

[2]Douglas B.West.Introduction to Graph Theory[M],China Machine Press,Second Edition,2006.

[3]赵彤.关于完全多部图的{C3，C4，C5}-强制分解[J].信阳师范学院学报(自然科学版),2004,17(4):389-392.

[4]赵彤.关于完全多部图Kn(t)的{C3，C5}-强制分解[J].铁道师院学报,2002,19(1):16-20.