完全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