(D3(4),λ)-支架和(D3(4),λ)-可分解的可分組設(shè)計(jì)的存在譜

楊 青, 鄭 義

(1.淮陰師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 江蘇 淮安 223300; 2.南京師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 江蘇 南京 210023)

0 引言及預(yù)備知識(shí)

V(H)和E(H)分別表示圖H的頂點(diǎn)集和邊集,λH表示重?cái)?shù)為λ的多重圖,K(m1,m2,…,mu)表示有u個(gè)部(組)的完全多部圖,Ku表示有u個(gè)頂點(diǎn)的完全圖.

設(shè)G是一些圖的集合,圖H的一個(gè)G-分解是指將E(H)劃分為H的一些同構(gòu)于G中的子圖(稱為區(qū)組).圖H的部分頂點(diǎn)不交且劃分V(H)的子圖稱為一個(gè)平行類.若平行類中的區(qū)組都同構(gòu)于某一個(gè)圖,則稱該平行類是一致的.若圖H存在一個(gè)G-分解,且所有區(qū)組可以被劃分為若干個(gè)平行類,則稱圖H存在一個(gè)可分解的G-分解.關(guān)于完全圖的G-分解有著廣泛研究[1-4].

圖λK(m1,m2,…,mu)的一個(gè)(可分解的)G-分解稱為(可分解的)可分組設(shè)計(jì),記作(G’,λ)-(R)GDD.當(dāng)λ=1時(shí),記號(hào)中λ可以省略,簡(jiǎn)記為G-(R)GDD;當(dāng)G’中只有一個(gè)圖G時(shí),將(G’,λ)-(R)GDD簡(jiǎn)記為(G,λ)-(R)GDD.(G’,λ)-(R)GDD的型是指完全多部圖中部大小的多重集,通常用1i2j3k…來表示,即有i個(gè)大小為1的部,j個(gè)大小為2的部,等等.

圖H的部分頂點(diǎn)不交且頂點(diǎn)集的并真包含于V(H)的子圖,稱為一個(gè)帶洞平行類.若型為gu的(G’,λ)-GDD的區(qū)組集可以被劃分為若干個(gè)帶洞平行類,每個(gè)帶洞平行類的點(diǎn)集都恰好缺少一個(gè)組上的點(diǎn),則稱該GDD是一個(gè)支架.支架設(shè)計(jì)在圖分解中起著關(guān)鍵性作用,關(guān)于組型一致支架的討論已經(jīng)有許多.如Colbourn 等人研究了(K2,λ)-支架的存在性[5];Chen F和Cao H完全解決了(K1,3,λ)-支架的存在譜[6];Cao等人著手研究了(Ck,1)-支架的存在性[7];Buratti等人完全解決了(CK,λ)-支架的存在譜[8];Stinson解決了(k3,1)-支架的存在譜[9];其他關(guān)于(k4,λ)-支架的研究也比較多[10-14].

本文主要研究G為D3(4)的支架和可分解的可分組設(shè)計(jì)的存在性問題,其中D3(4)為完全圖K4去掉一個(gè)一因子,即點(diǎn)集為{a,b,c,d}的完全圖去掉邊{a,d}和{b,d}后得到的圖.為方便起見,以下用(a,b,c,d)表示D3(4).當(dāng)然,也有其他關(guān)于此類圖的標(biāo)記[15-16].

引理1 若型為gu的(D3(4),λ))-支架存在,則

λg≡0(mod 2),g(u-1)≡0(mod 4),u≥4, 且當(dāng)u=4時(shí),g≡0(mod 4).

引理2[17]型為gu的D3(4)-支架存在,當(dāng)且僅當(dāng)

u≥4,g(u-1)≡0(mod 4),g≡0(mod 2).

引理3 若型為gu的(D3(4),λ))-RGDD存在,則

λg(u-1)≡0(mod 2),gu≡0(mod 4),u≥3, 且當(dāng)u=3時(shí),g≡0(mod 4).

引理4[18]型為gu的D3(4)-RGDD存在,當(dāng)且僅當(dāng)

u≥3,g(u-1)≡0(mod 2),g≡0(mod 4).

下面將對(duì)任意相遇數(shù)λ,解決(D3(4),λ)-支架與(D3(4),λ)-RGDD這兩類設(shè)計(jì)的存在性.

1 (D3(4),λ)-支架的存在譜

設(shè)K是一個(gè)正整數(shù)集,若G’={K1,K2,…,Kt},其中|V(Ki)|∈K(1≤i≤t),則將G’-GDD記為K-GDD,型為1v的K-GDD稱為成對(duì)平衡設(shè)計(jì),記作(K,v)-PBD.當(dāng)K={k}時(shí),簡(jiǎn)記為k-GDD.

接下來,將用到以下遞推構(gòu)造方法,類似的證明過程[9,19]略.首先,介紹一個(gè)定義.給定一個(gè)圖G,字典積G[n]的點(diǎn)集是

{xi|x∈V(G),i∈Zn}, 且{xi,yi}∈E(G[n]),i,j∈Zn當(dāng)且僅當(dāng){x,y}∈E(G).

引理5 對(duì)任意m≥1且m≠2,6,存在圖D3(4)[m]的D3(4)-分解.

證明由(K3,1)-RGDD(m3)可得其存在性[5].設(shè)其組為{x}×Zn,x∈{a,b,c}.將其m個(gè)平行類標(biāo)記為

由文[5]知,K3[m]有1-因子分解,設(shè)其組為{y}×Zn,y∈{c,d},1-因子為

設(shè)圖D3(4)[m]的點(diǎn)集為{a,b,c,d}×Zn,

令

容易驗(yàn)證R1,R2,…,Rm即為所需的分解.

接下來，解決(D3(4),λ)-支架的存在性問題.由引理1可知，只需解決λ=1和λ=2的情形.前者已經(jīng)由引理2解決,下面解決λ=2的情形.

引理6 對(duì)任意u≥5且u≡1(mod) 4,存在型為1u的(D3(4),2)-支架.

證明對(duì)u∈{5,9,13},設(shè)頂點(diǎn)集為Zu,組為Mi={i},i∈Zu.缺掉組Mi的帶洞平行類是{P+i},其中P中的區(qū)組如下.

u=5,P:{2,3,1,4},

u=9,P:{2,4,1,5},{3,7,6,8},

u=13,P:{2,3,1,5},{7,10,4,9},{8,12,6,11}.

對(duì)任意u≥17,存在一個(gè)型為4(u-1)/4的D3(4)-支架[17],將每個(gè)區(qū)組重復(fù)一次可得一個(gè)型為4(u-1)/4的(D3(4),2)-支架.運(yùn)用構(gòu)造3,其中當(dāng)ε=1時(shí),可得型為1u的(D3(4),2)-支架,其中的輸入設(shè)計(jì)型為15的(D3(4),2)-支架在證明中已經(jīng)構(gòu)造.

定理1 型為gu的(D3(4),λ)-支架存在,當(dāng)且僅當(dāng)

λg≡0(mod 2),g(u-1)≡0(mod 4),u≥4.

證明分兩種情形:

情形1:λ≡1(mod 2),λ=1的情形見引理2,將λ=2其每個(gè)區(qū)組重復(fù)λ次得到型為gu的(D3(4),2)-支架.

情形2:λ≡0(mod 2).分以下3種情況考慮λ=2:

1)g≡1(mod 2),且u≡1(mod 4),u≥5.

由引理5知,D3(4)[g]有D3(4)-分解.由引理6知,存在型為1u的(D3(4),2)-支架.取m=g并運(yùn)用構(gòu)造1可得型為gu的((D3(4),2)-支架.

2)g≡2(mod 4),且u≡1(mod 2),u≥5.

由引理2知,存在型為gu的D3(4)-支架.將其每個(gè)區(qū)組重復(fù)兩次即可得型為gu的(D3(4),2)-支架.

3)g≡0(mod 4),且u≥4.

由引理2知,存在型為gu的D3(4)-支架.將其每個(gè)區(qū)組重復(fù)兩次即可得型為gu的(D3(4),2)-支架.

2 (D3(4),λ)-RGDD的存在譜

首先，給出一些(D3(4),λ)-RGDD的遞推方法.

構(gòu)造4[1,6,19]若存在型為gu的(G,λ)-RGDD,且G[m]有G-因子分解,則存在型為(mg)u的(G,λ)-RGDD.

構(gòu)造5[1,6,19]若同時(shí)存在型為(gu)l和gu的(G,λ)-RGDD,則存在型為gul的(G,λ)-RGDD.

對(duì)(D3(4),λ)-RGDD(gu)的存在性,由引理3可知，僅需考慮λ=1和λ=2的情況.前者已由引理4解決.下面解決λ=2.

引理7 存在一個(gè)型為4u的(D3(4),2)-RGDD,其中u≥3.

證明由引理4可知存在D3(4)-RGDD,將其區(qū)組重復(fù)一次可得所求設(shè)計(jì).

引理8 對(duì)任意u≥4且u≡0(mod 2),存在型為2u的(D3(4),2)-RGDD.

證明由引理4可知存在D3(4)-RGDD,將其區(qū)組重復(fù)一次可得所求設(shè)計(jì).

引理9 對(duì)任意u≥4且u≡0(mod 4),存在型為1u的(D3(4),2)-RGDD.

證明對(duì)u=4，8,設(shè)點(diǎn)集為Zu-1∪{∞0},組為{i},i∈Zu-1和{∞0}.所需的u-1個(gè)平行類可以從一個(gè)已知的平行類P通過+1(modu-1)生成.P中的區(qū)組如下:

u=4,P：{0,1,2,∞0},

u=8,P：{4,0,1,2},{5,3,6,∞0}.

定理2 型為gu的(D3(4),λ)-RGDD存在,當(dāng)且僅當(dāng)

λg(u-1)≡0(mod 2),gu≡0(mod 4),u≥3.

證明下面分兩種情形證明.

情形1:λ≡1(mod 2).由引理4可知,存在(D3(4),1)-RGDD(gu),將其區(qū)組重復(fù)λ次即得(D3(4),λ)-RGDD(gu).

1)g≡1(mod 2).此時(shí)u≡0(mod 4),u≥4,令m=g,運(yùn)用構(gòu)造4,利用引理9中的輸入設(shè)計(jì)型為1u的(D3(4),2)-RGDD,可得型為gu的(D3(4),λ)-RGDD.

2)g≡2(mod 4).此時(shí)u≡0(mod 2),u≥4.由引理4可知,存在(D3(4),1)-RGDD(gu),將其區(qū)組重復(fù)2次即得(D3(4),2)-RGDD(gu).

3)g≡0(mod 4).此時(shí)u≥3.由引理4可知,存在(D3(4),1)-RGDD(gu),將其區(qū)組重復(fù)2次即得(D3(4),2)-RGDD(gu).

3 總結(jié)

本文對(duì)任意相遇數(shù)λ,研究了圖D3(4)的兩類設(shè)計(jì)的存在性.主要結(jié)果如下:

1) 型為gu的(D3(4),λ)-支架存在的充要條件為λg≡0(mod 2),g(u-1)≡0(mod 4),u≥4,且當(dāng)u=4時(shí),g≡0(mod 4);

2) 型為gu的(D3(4),λ)-RGDD存在的充要條件為λg(u-1)≡0(mod 2),gu≡0(mod 4),u≥3,且當(dāng)u=3時(shí),g≡0(mod 4).