完全r部图Kr(t)的{C3,C2k}-强制分解(k≥4)的渐近存在性

骆汝九

(连云港职业技术学院,江苏连云港 222006)

完全r部图Kr(t)的{C3,C2k}-强制分解(k≥4)的渐近存在性

骆汝九

(连云港职业技术学院,江苏连云港 222006)

研究基于顶点集V=Vi(其中|Vi|=t,i=1,2,…,r)的完全r部图Kr(t) 的3圈和2k圈{C3,C2k}-强制分解(k≥4)的存在性问题.通过构造并运用Kr(t)的两种分解法,证明了Kr(t)的{C3,C2k}-强制分解(k≥4)的渐近存在性,即对于任意给定的正整数k≥4,存在常数r0(k)=5k+2,使得当r≥r0(k)时,Kr(t)的{C3,C2k}-强制分解存在的必要条件也是充分的.

完全多部图;强制圈分解;渐近存在性

1 引言与主要结果

我们研究完全r部图Kr(t)的{C3,C2k}-分解,若规定在分解中C3和C2k必须同时存在,则称这样的分解为Kr(t)的{C3,C2k}-强制分解.1988年,文[2]提出并研究了强制成对平衡设计MR(L;v)的存在性问题.一个MR(L;v)是一个参数为(v,L,1)的成对平衡设计,∀l∈L,至少存在一个容量为l的区组.用图分解的术语,MR(L;v)即为完全图Kv的{Kl:l∈L}-强制分解.

作者在文[3]中已给出Kr(t)的{C3,C2k}-强制分解(k≥2)存在的必要条件,得到下面的定理.

定理A若完全r部图Kr(t)的{C3,C2k}-强制分解存在,则r与t必须同时满足下列条件:

(i)r≥3;(ii)rt≥2k;(iii)r≡1(mod 2)或者t≡0(mod 2);(iv)存在p,q∈N,使得r(r−1)t2/2=3p+2kq.

特别地,文[3]证明了k=2,3时Kr(t)的{C3,C2k}-强制分解存在的必要条件也是充分的,从而给出了Kr(t)的{C3,C4}-强制分解和{C3,C6}-强制分解的存在性问题的完全解.

本文进一步讨论k≥4时,Kr(t)的{C3,C2k}-强制分解的存在性问题,证明了它的渐近存在性,得到了下面的主要结果.

定理1.1对于任意给定的正整数k≥4,存在常数r0(k)=5k+2,当r≥r0(k)时,完全r部图Kr(t)的{C3,C2k}–强制分解存在的必要且充分条件为:

(i)r≡1(mod 2)或者t≡0(mod 2);(ii)存在p,q∈N,使得r(r−1)t2/2=3p+2kq.

注1.1当r≥r0(k)=5k+2时,定理A中的条件(i)、(ii)自然成立.

我们首先给出k/≡0(mod 3)和k≡0(mod 3)时定理1.1中条件(i)、(ii)的等价形式,在此基础上,证明定理1.1.在数……