完全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.在数论中已证明:对于任意正整数a,b,c,若a,b互素,则当c＞ab时,方程ax+by= c一定存在正整数解.因此,若k/≡0(mod 3),此时3与2k互素,则当r(r−1)t2/2＞6k时,定理1.1中的条件(ii)恒成立.因为r≥r0(k)=5k+2时,一定有r(r−1)t2/2＞6k,所以k/≡0(mod 3)时,只需证明定理1.1中的条件(i)成立即可.

若k≡0(mod 3),经演算易证定理1.1的条件(i)、(ii)等价于下列表达式:

(i)当r≡1,3(mod 6)时,t≥1;(ii)当r≡0,4(mod 6)时,t≡0(mod 2);(iii)当r≡2(mod 6)时,t≡0(mod 6);(iv)当r≡5(mod 6)时,t≡0(mod 3).(1.1)

2 基本引理

3 定理1.1的证明

在定理1.1的证明中,本文构造并需多次使用完全r部图Kr(t)的两种分解法,为叙述方便,分别称之为型Ⅰ分解法和型Ⅱ分解法.

于是,{Kr1+1(t),Kr2+1(t),Kr1t,r2t}形成完全r部图Kr(t)的一个分解.

下面我们证明定理1.1.首先讨论k≥4且k/≡0(mod 3)的情形,此时k≡1,2,4,5(mod 6).由前面的讨论可知,只需证明定理1.1中的条件(i)成立.

引理3.1若k≡1(mod 6),令r0(k)=(5k+1)/2,则当r≥r0(k)时,∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

证明设l∈N∪{0},下同.

考虑完全多部图K(5k+1)/2+3l(2)、K(3k+5)/2+3l(2)和K(3k+1)/2+3l(2)的{C3,C2k}-强制分解

的存在性.

(i)用型Ⅰ法,将K(5k+1)/2+3l(2)分解成一个K(k+1)/2+3l(2)、一个K2k(2)和一个Kk+6l+1,4k,再将其中的K2k(2)分解成二个Kk(2)和一个K2k,2k.

由于(k+1)/2+3l≡1(mod 3),k≡1(mod 3),由引理2.1知,K(k+1)/2+3l(2)和Kk(2)的C3-分解均存在;由引理2.2知,Kk+6l+1,4k和K2k,2k的C2k-分解存在;因此,K(5k+1)/2+3l(2)的{C3,C2k}-强制分解存在.

(ii)用型Ⅰ法,将K(3k+5)/2+3l(2)分解成一个K(k+5)/2+3l(2)、一个Kk(2)和一个Kk+6l+5,2k.

由于(k+5)/2+3l≡0(mod 3),k≡1(mod 3),由引理2.1知,K(k+5)/2+3l(2)和Kk(2)的C3-分解均存在;由引理2.2知,Kk+6l+5,2k的C2k-分解存在;因此,K(3k+5)/2+3l(2)的{C3,C2k}-强制分解存在.

(iii)用型Ⅰ法,将K(3k+1)/2+3l(2)分解成一个K(k+1)/2+3l(2)、一个Kk(2)和一个Kk+6l+1,2k.

由于(k+1)/2+3l≡1(mod 3),k≡1(mod 3),由引理2.1知,K(k+1)/2+3l(2)和Kk(2)的C3-分解均存在;由引理2.2知,Kk+6l+1,2k的C2k-分解存在;因此,K(3k+1)/2+3l(2)的{C3,C2k}-强制分解存在.

注意到r=(5k+1)/2+3l≡0(mod 3),r=(3k+5)/2+3l≡1(mod 3),r=(3k+1)/2+ 3l≡2(mod 3)以及l∈N∪{0}的任意性,令r0(k)=max{(5k+1)/2,(3k+5)/2,(3k+1)/2}= (5k+1)/2,则当r≥r0(k)时,完全多部图Kr(2)的{C3,C2k}-强制分解存在.

再由引理2.3知,∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

以下引理证法类似,不再作详细叙述.

引理3.2若k≡2(mod 6),令r0(k)=3k/2,则当r≥r0(k)时,∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

证明考虑完全多部图K3k/2+3l(2)、Kk+3l+2(2)和Kk+3l(2)的{C3,C2k}-强制分解的存在性.

用型Ⅰ法:

将K3k/2+3l(2)分解成一个Kk/2+3l(2)、一个Kk(2)和一个Kk+6l,2k,再将其中的Kk(2)分解成二个Kk/2(2)和一个Kk,k;

将Kk+3l+2(2)分解成一个K(k+4)/2+3l(2)、一个Kk/2(2)和一个Kk+6l+4,k;

将Kk+3l(2)分解成一个Kk/2+3l(2)、一个Kk/2(2)和一个Kk+6l,k.

类似引理3.1的证法,易证:K3k/2+3l(2)、Kk+3l+2(2)和Kk+3l(2)的{C3,C2k}-强制分解存在.

令r0(k)=max{3k/2,k+2,k}=3k/2,即得结论.

引理3.3若k≡4(mod 6),令r0(k)=3k/2+1,则当r≥r0(k)时,∀m∈N,Kr(2m)的{C3, C2k}-强制分解存在.

证明考虑完全多部图Kk+3l+2(2)、K3k/2+3l+1(2)和Kk+3l+1(2)的{C3,C2k}-强制分解的存在性.

用型Ⅱ法,将Kk+3l+2(2)分解成一个K(k+4)/2+3l(2)、一个K(k+2)/2(2)和一个Kk+6l+2,k;

易证:Kk+3l+2(2)、K3k/2+3l+1(2)和Kk+3l+1(2)的{C3,C2k}–强制分解存在.

令r0(k)=max{k+2,3k/2+1,k+1}=3k/2+1,即得结论.

引理3.4若k≡5(mod 6),令r0(k)=(5k+1)/2,则当r≥r0(k)时,∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

令r0(k)=max{(3k+3)/2,(5k+1)/2,(3k+7)/2}=(5k+1)/2,即得结论.

综合引理3.1、引理3.2、引理3.3及引理3.4,得到下面的结论.

定理3.1若k≥4且k/≡0(mod 3),令r0(k)=(5k+1)/2,则当r≥r0(k)时,∀m∈N,Kr(2m) 的{C3,C2k}-强制分解存在,即对于t≡0(mod 2),Kr(t)的{C3,C2k}-强制分解存在.

由定理3.1及引理2.4,得下面的定理.

定理3.2若k≥4且k/≡0(mod 3),令r0(k)=5k+2,则当r≥r0(k)且r≡1(mod 2)时,∀t∈N,Kr(t)的{C3,C2k}-强制分解存在.

综合定理3.1和定理3.2,完成了本文主要结果(定理1.1)当k/≡0(mod 3)时的证明.

下面讨论k≥4且k≡0(mod 3)的情形,此时定理1.1的条件(i)、(ii)等价于表达式(1.1).

引理3.5若k≡0(mod 3),令r0(k)=(3k+5)/2,则当r≥r0(k)且r≡0,1(mod 3)时,∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

证明(i)若k≡0(mod 6),此时考虑完全多部图Kk+3l(2)和Kk+3l+1(2)的{C3,C2k}-强制分解的存在性,这里r=k+3l≡0(mod 3),r=k+3l+1≡1(mod 3).

用型Ⅰ法:

易证:Kk+3l(2)和Kk+3l+1(2)的{C3,C2k}-强制分解存在.

令r0(k)=max{k,k+1}=k+1,则当r≥r0(k)且r≡0,1(mod 3)时,∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

(ii)若k≡3(mod 6),此时考虑完全多部图K(3k+3)/2+3l(2)和K(3k+5)/2+3l(2)的{C3,C2k}-强制分解的存在性,这里r=(3k+3)/2+3l≡0(mod 3),r=(3k+5)/2+3l≡1(mod 3).

用型Ⅰ法:

令r0(k)=max{(3k+3)/2,(3k+5)/2}=(3k+5)/2,则当r≥r0(k)且r≡0,1(mod 3)时, ∀m∈N,Kr(2m)的{C3,C2k}-强制分解存在.

综合(i)、(ii),令r0(k)=max{k+1,(3k+5)/2}=(3k+5)/2,即得结论.

注3.1若r≡0,4(mod 6),则一定有r≡0,1(mod 3),因此当r≡0,4(mod 6)时,引理3.5的结论成立,即证得(1.1)式中的条件(ii).

由引理3.5及引理2.4,得下面的引理.

引理3.6若k≡0(mod 3),令r0(k)=3k+6,则当r≥r0(k)且r≡1,3(mod 6)时,∀t∈N, Kr(t)的{C3,C2k}-强制分解存在.

注3.2由引理3.6,(1.1)式中的条件(i)得证.

引理3.7若k≡0(mod 3),令r0(k)=k+5,则当r≥r0(k)且r≡2(mod 6)时,∀m∈N, Kr(6m)的{C3,C2k}-强制分解存在.

证明(i)若k≡0(mod 6),此时考虑完全多部图Kk+6l+2(6)的{C3,C2k}-强制分解的存在性,这里r=k+6l+2≡2(mod 6).

由引理2.6知,K(k+15)/3+6l(3)和K(2k+3)/3(3)的C3-分解均存在;由引理2.2知,Kk+18l+12,2k的C2k-分解存在;因此,Kk+6l+5(3)的{C3,C2k}-强制分解存在.令r0(k)=k+5,则当r≥r0(k)且r≡5(mod 6)时,∀m∈N,Kr(3m)的{C3,C2k}-强制分解存在.

(ii)若k≡3(mod 6),此时考虑完全多部图Kk+6l+2(3)的{C3,C2k}-强制分解的存在性,这里r=k+6l+2≡5(mod 6).

综合(i)、(ii),令r0(k)=max{k+5,k+2}=k+5,即得结论.

注3.4由引理3.8,(1.1)式中的条件(iv)得证.

综合引理3.5-引理3.8,完成了本文主要结果(定理1.1)当k≡0(mod 3)时的证明.

综上,对于任意给定的正整数k≥4,令r0(k)=5k+2,则当r≥r0(k)时,Kr(t)的{C3,C2k}-强制分解存在的必要条件也是充分的,于是定理1.1得证.

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].London:The Macmillan Press Ltd,1976.

[2]Mendelsohn E,Rees R.Mandatory representation designs[J].Combinatorial Theory(Series A),1988,49: 349-362.

[3]骆汝九.完全r部图Kr(t)的{C3,C2k}-强制分解[J].工程数学学报,2007,24(4):753-756.

[4]Collbourn C J,Dinitz J H.The CRC Handbook of Combinatorial Designs[M].Boca Raton,FL:CRC Press, 1996.

[5]Sotteau D.Decomposition of Km,n(K∗m,n)into cycles(circuits)of length 2k[J].Combinatorial Theory(Series B),1981,30:75-81.

Mandatory decompositions of complete multipartite graphs into cycles of lengths 3 and 2k(k≥4)

LUO Ru-jiu
(Lianyungang Technical College,Lianyungang222006,China)

In this paper,the existence problem of a{C3,C2k}–mandatory decomposition of Kr(t)was discussed. Through constructing and applying two decomposition methods of Kr(t),the paper proved that the necessary conditions for the existence of a{C3,C2k}–mandatory decomposition of Kr(t)(k≥4)are also sufficient whenever r≥5k+2.

complete multipartite graphs,mandatory decomposition,cycles

O157.5

A

1008-5513(2009)03-0470-05

2008-02-29.

江苏省教育厅高校“青蓝工程”基金(苏教师[2005]12).

骆汝九(1967-),博士生,副教授,研究方向:组合数学,试验统计.

2000MSC:05C15