區(qū)組為K4-e的可分組核心設(shè)計

高玉峰, 馮 弢

(1. 北京交通大學 理學院, 北京 100044； 2. 通化師范學院 數(shù)學學院, 吉林 通化 134000)

1 引言與預備知識

組合設(shè)計理論中的核心設(shè)計[1]在圖分解、 圖填充和圖覆蓋等問題中應用廣泛. Mendelsohn等[1]首先提出了核心設(shè)計的概念, 并解決了區(qū)組長度為3核心設(shè)計的存在性問題. 本文將核心設(shè)計的概念推廣到可分組核心設(shè)計.

設(shè)H是一個簡單圖,Γ是一個簡單圖的集合. 設(shè)X是H的點集, A,B是H子圖的集合, A,B中的元素稱為區(qū)組. 如果每個區(qū)組都同構(gòu)于Γ中的一個圖, 且H的每條邊都包含在A的至多一個區(qū)組中, 則稱(X,A)為一個(H,Γ)-填充. 如果每個區(qū)組都同構(gòu)于Γ中的一個圖, 且H的每條邊都包含在B的至少一個區(qū)組中, 則稱(X,B)為一個(H,Γ)-覆蓋. 如果Γ只包含一個簡單圖G, 則記為(H,G)-填充或(H,G)-覆蓋.

對于(H,G)-填充(X,A), 如果不存在(H,G)-填充(X,D)使得|D|>|A|, 則稱該(H,G)-填充(X,A)是最大的. 由H中所有不包含在A區(qū)組中的邊構(gòu)成的圖(X,L)稱為(H,G)-填充(X,A)的余邊圖, 簡稱余邊. 對于(H,G)-覆蓋(X,B), 如果不存在(H,G)-覆蓋(X,D)使得|D|<|B|, 則稱該(H,G)-覆蓋(X,B)是最小的. 由H中所有包含在B的至少兩個區(qū)組中的邊構(gòu)成的圖(X,E)稱為(H,G)-覆蓋(X,B)的超邊圖, 簡稱超邊. 如果一個(H,G)-填充的余邊是空的, 則該填充是最大的； 如果一個(H,G)-覆蓋的超邊是空的, 則該覆蓋是最小的, 此時稱為(H,G)-設(shè)計.

Billington等[2]給出了型為gn的K3-MGDP存在的充分必要條件, 并驗證了所有可能的余邊;Hu等[3]考慮帶所有可能余邊的型為gn的(K3+e)-MGDP存在性, 其中K3+e為三角K3帶一條懸邊, 解決了帶所有可能超邊的型為gn的(K3+e)-MGDC的存在性;Fort等[4]解決了型為1n的K3-MGDC的存在性問題;Heinrich等[5]推廣了文獻[4]的結(jié)果, 確定了型為gn的K3-MGDC存在的充分必要條件, 并給出了一種可能超邊的存在性.

定義1設(shè)H,G為簡單圖, (X,A)為任意的最大(H,G)-填充, (X,B)為任意的最小(H,G)-覆蓋, 令C=A∩B, 當|C|最大時, 稱(X,C)為一個(H,G)-核心設(shè)計. 一個(Ku1,u2,…,ut,G)-核心設(shè)計稱為可分組的G-核心設(shè)計, 記作型為{u1,u2,…,ut}的G-GDND.

這些邊生成的所有可能余邊列于表1.

表1 組型為gn的(K4-e)-MGDP可能的余邊

這些邊生成所有可能的超邊列于表2. 表1和表2中的Ei表示由i(i=1,2,3,4)條邊組成的任意簡單圖. 易知E1為一條單邊. 圖1為E2,E3,E4所有可能的簡單圖, 其中Ei,j中的i(i=2,3,4)表示邊數(shù),j(1≤j≤11)為序號.

表2 組型為gn的(K4-e)-MGDC可能的超邊

圖1 含有2條邊、 3條邊、 4條邊的簡單圖Fig.1 Simple graphs with 2 edges, 3 edges and 4 edges

Colbourn等[6]確定了型為gn的(K4-e)-GDD存在的充分必要條件;Hoffman等[7]研究了帶所有可能余邊的型為1n的(K4-e)-MGDP的存在性;Lindner等[8]給出了帶所有可能超邊的型為1n的(K4-e)-MGDC的存在性. 將型為gn的(K4-e)-GDND區(qū)組數(shù)記為N(gn), 由定義易知

本文利用直接構(gòu)造和遞歸構(gòu)造的方法, 討論型為gn的(K4-e)-MGDP和(K4-e)-MGDC的存在性, 并確定型為gn的(K4-e)-GDND的存在性.

2 不完全可分組設(shè)計及相關(guān)構(gòu)造

考慮兩種不同結(jié)構(gòu)的K4-e不完全可分組設(shè)計, 并討論其在(K4-e)-GDND構(gòu)造中的應用.

2.1 型為g(n,h)的K4-e不完全可分組設(shè)計

一個型為gn-h(gh)1的G-GDD稱為一個型為g(n,h)的不完全G-GDD, 簡寫為型為g(n,h)的G-IGDD. 大小為gh的組稱為IGDD的洞. 用一個型為gh的G-GDP填一個型為g(n,h)的G-IGDD的洞, 可得一個型為gn的G-GDP. 用一個型為gh的G-GDC填一個型為g(n,h)的G-IGDD的洞, 可得一個型為gn的G-GDC.

構(gòu)造1假設(shè)存在型為g(n,h)的G-IGDD. 如果存在型為gh的G-GDND, 則可得型為gn的G-GDND.

證明: 設(shè)型為gh的G-GDND(X,C)是由型為gh的G-MGDP(X,A)和型為gh的G-MGDC(X,B)得到的, C=A∩B. 設(shè)型為g(n,h)的G-IGDD為(X,D). 用型為gh的G-MGDP(X,A)填型為g(n,h)的G-IGDD(X,D)的洞, 可得型為gn的G-MGDP(X,A∪D). 用型為gh的G-MGDC(X,B)填型為g(n,h)的G-IGDD(X,D)的洞, 可得型為gn的G-MGDC(X,B∪D). 用型為gh的G-GDND(X,C)填型為g(n,h)的G-IGDD(X,D)的洞, 可得(X,C∪D). 由

(A∪D)∩(B∪D)=(A∩B)∪D=C∪D

可知, (X,C∪D)是一個型為gn的G-GDND.

引理1[9]對于滿足g(h+2)≡0(mod4)和h≡0(mod2)的任意正整數(shù)g,h, 總存在型為g((3h+2)/2,h)的(K4-e)-IGDD.

引理2[9]對于g,h∈{2,3,4}, 存在型為g(5+h,h)的(K4-e)-IGDD.

引理3[9]對于(g,n,h)∈{(2,14,7),(11,8,3)}, 存在型為g(n,h)的(K4-e)-IGDD.

構(gòu)造2[9]假設(shè)存在型為g(n,h)的(K4-e)-IGDD, 則存在型為(gt)(n,h)的(K4-e)-IGDD, 其中t≥1.

對于n∈{12,14}, 型為1(n,4)的(K4-e)-IGDD是存在的[7], 由構(gòu)造2可得如下引理.

引理4令n∈{12,14}, 對任意的g≥1, 總存在型為g(n,4)的(K4-e)-IGDD.

由文獻[10]中可分組設(shè)計的標準填洞構(gòu)造變形可得如下引理.

引理5[10]令n≡h(mod5), n≥15+h, 如果存在型為g(5+h,h)的(K4-e)-IGDD, 則存在型為g(n,5+h)和型為g(n,h)的(K4-e)-IGDD.

2.2 型為(g,h)n的K4-e的不完全可分組設(shè)計

令S為完全n部圖Kn(g)點集的子集, S帶分部的集合Gi(1≤i≤n), 滿足|Gi∩S|=h. 令K[S]為由S誘導的Kn(g)的子圖. 稱(Kn(g)K[S],G)-設(shè)計為不完全的可分組設(shè)計, 記作型為(g,h)n的G-IGDD, S稱為洞.

例1在I12上構(gòu)造一個型為(4,1)3的(K4-e)-IGDD, 組為{i,i+3,i+6,i+9}, 0≤i≤2, 洞集合為S={0,1,2}. 所有的區(qū)組為： {[5,4,0-3],[7,8,0-6],[10,11,0-9],[5,6,1-10],[3,11,1-7],[8,9,1-4],[7,9,2-5],[3,10,2-8],[4,6,2-11]}.

類似構(gòu)造1, 下面給出利用型為(g,h)n的G-IGDD構(gòu)造G-GDND的基本方法.

構(gòu)造3假設(shè)存在型為(g,h)n的G-IGDD. 如果存在型為hn的G-GDND, 則可得型為gn的G-GDND.

例2已知存在型為(4,1)4的(K4-e)-IGDD[9]和型為14的(K4-e)-GDND[7], 運用構(gòu)造3可得型為44的(K4-e)-GDND.

構(gòu)造4假設(shè)存在型為(g,h)n的(K4-e)-IGDD, 則存在型為(gt,ht)n的(K4-e)-IGDD, 其中t≥1.

引理6[9]令g≡r(mod5), g≥15+r, 如果存在型為(5+r,r)n的(K4-e)-IGDD, 則存在型為(g,5+r)n和型為(g,r)n的(K4-e)-IGDD.

引理7[9]令g(n-1)≡0(mod2), n≥3, 存在型為(3g,2g)n的(K4-e)-IGDD.

引理8[9]令n≥3, n≠6, 對于(g,h)∈{(4,1),(7,3),(13,7)}, 存在型為(g,h)n的(K4-e)-IGDD. 令n≥3, n≠6,8, 存在型為(11,1)n的(K4-e)-IGDD.

引理9[9]令r∈{2,3,4}, 存在型為(5+r,r)8的(K4-e)-IGDD. 令r∈{1,2,3,4}, n≥3, n≠6, 存在型為(5+r,r)n的(K4-e)-IGDD.

引理10[9]令n≡1,3(mod6), n≥3, 存在型為(11,6)n的(K4-e)-IGDD.

3 可分組核心設(shè)計的直接構(gòu)造與遞歸構(gòu)造

由核心設(shè)計定義可知, 如果由型為gn的(K4-e)-MGDP(X,A)和(K4-e)-MGDC(X,B)可得型為gn的(K4-e)-GDND(X,C), 則

因此, 假設(shè)由型為gn的(K4-e)-MGDP(X,A)和(K4-e)-MGDC(X,B)可得(X,C), C=A∩B, 如果

則此時|C|一定最大, 因此(X,C)是一個型為gn的(K4-e)-GDND. 如果

則此時|C|也一定最大, 因此(X,C)是一個型為gn的(K4-e)-GDND. 下面給出可分組設(shè)計的直接構(gòu)造和遞歸構(gòu)造.

1) g=1,2,3,4的情形.

引理11對于n∈{3,4,7,8,9,12,13,14}, 存在型為2n的(K4-e)-GDND.

證明: 令點集X=I2n, 組的集合為{{i,i+n}: 0≤i≤n-1}.

當n=3時, 已知帶余邊E2,1的型為23的(K4-e)-MGDP不存在, 帶余邊E2,2的型為23的(K4-e)-MGDP(X,A)存在, 且兩條邊的4個點只出現(xiàn)在兩個組中[9]. 因此, 不能通過將A與一個區(qū)組求并的形式得到型為23的(K4-e)-MGDC. 所以, N(23)≤D(23)-1. 令

則|C|=|A|-1. 令

可知(X,A)是帶余邊E2,2的型為23的(K4-e)-MGDP, (X,B)是帶超邊E3,5的型為23的(K4-e)-MGDC, 則(X,C)是型為23的(K4-e)-GDND.

當n=4時, 令

可知(X,A)是帶余邊E4,2的型為24的(K4-e)-MGDP, (X,B)是帶有超邊E6的型為24的(K4-e)-MGDC, 則(X,C)是型為24的(K4-e)-GDND.

當n=7時, 令A=C, 區(qū)組為： {[0,8,6-13],[1,9,6-13],[2,10,6-13],[3,11,6-13],[4,12,6-13],[5,7,6-13],[0,2,4-5],[0,9,3-11],[0,1,10-12],[1,2,7-11],[1,5,3-4],[2,3,8-12],[4,7,3-10],[5,10,8-11],[8,9,4-7],[11,12,7-8]}. 令

B=C∪{[9,10,12-5]}, E4,1={{5,9},{9,10},{9,12},{10,12}}, E1={{5,10}}.

可知(X,A)是帶余邊E4,1的型為27的(K4-e)-MGDP, (X,B)是帶超邊E1的型為27的(K4-e)-MGDC, 則(X,C)是型為27的(K4-e)-GDND.

當n=8時, 令A=C, 區(qū)組為： {[0,3,2-4],[0,6,5-7],[0,10,9-11],[12,13,0-1],[14,15,0-1],[1,4,2-5],[1,6,3-10],[7,11,1-2],[2,8,5-6],[2,12,9-14],[13,15,2-3],[3,7,5-9],[9,15,5-6],[4,10,8-15],[10,12,3-7],[10,14,5-13],[4,14,9-11],[8,14,3-7],[4,13,6-7],[11,12,5-6],[9,13,8-11],[8,15,11-12]}. 令

可知(X,A)是帶余邊E2,1的型為28的(K4-e)-MGDP, (X,B)是帶超邊E3,2的型為28的(K4-e)-MGDC, 則(X,C)是型為28的(K4-e)-GDND.

當n=9時, 令A=C, 區(qū)組為： {[0,4,3-5],[0,7,6-8],[0,12,11-13],[14,15,0-1],[16,17,0-1],[1,5,3-6],[1,7,4-9],[8,12,1-2],[11,13,1-3],[2,6,3-4],[2,7,5-10],[2,13,9-16],[2,17,14-15],[3,14,7-8],[3,10,9-17],[15,16,3-4],[4,9,8-17],[10,12,4-6],[11,14,4-10],[5,15,8-12],[9,16,5-6]，[10,13,5-15],[11,17,5-6],[6,13,8-14],[11,15,7-9],[7,17,12-13],[8,16,10-11],[12,14,9-16]}. 令

可知(X,A)是帶余邊E4,1的型為29的(K4-e)-MGDP, (X,B)是帶超邊E1的型為29的(K4-e)-MGDC, 則(X,C)是型為29的(K4-e)-GDND.

當n=12時, 令A=C, 區(qū)組為： {[0,4,5-6],[0,7,8-9],[0,10,11-13],[0,14,15-16],[0,17,18-19],[20,21,0-1],[22,23,0-1],[1,3,4-7],[1,6,5-17],[1,8,9-14],[1,10,12-15],[11,16,1-2],[18,19,1-2],[2,3,5-10],[4,8,2-10],[7,10,5-17],[9,10,6-18],[10,14,19-20],[10,16,21-23],[2,9,12-13],[2,15,6-17],[2,7,20-23],[21,22,2-3],[6,7,11-16],[4,7,12-14],[7,13,15-21],[18,22,4-7],[4,11,9-21],[4,13,17-19],[4,15,20-23],[5,9,14-15],[8,15,11-21],[12,15,16-18],[19,22,5-15],[5,18,8-21],[5,13,11-16],[5,12,20-23],[3,16,8-18],[11,14,3-18],[13,18,20-23],[12,19,11-21],[11,20,17-22],[16,22,9-17],[19,20,6-16],[8,23,17-19],[14,17,12-21],[6,23,14-21],[3,9,17-19],[20,23,3-9],[13,22,8-14],[6,12,8-22],[3,13,6-12]}. 令

可知(X,A)是帶余邊E4,1的型為212的(K4-e)-MGDP, (X,B)是帶超邊E1的型為212的(K4-e)-MGDC, 則(X,C)是型為212的(K4-e)-GDND.

當n=13時, 由引理1可知, h=8滿足引理條件, 因此存在型為2(13,8)的(K4-e)-IGDD. 已知存在型為28的(K4-e)-GDND, 利用構(gòu)造1可得型為213的(K4-e)-GDND. 當n=14時, 由引理3可知, 存在型為2(14,7)的(K4-e)-IGDD. 已知存在型為27的(K4-e)-GDND, 利用構(gòu)造1可得型為214的(K4-e)-GDND.

引理12對于n∈{3,4,7,8,9,12,13,14}, 存在型為3n的(K4-e)-GDND.

證明: 令點集X=I3n, 組的集合為{{i,i+n,i+2n}: 0≤i≤n-1}.

當n=3時, 易知N(33)≤D(33)-1[9]. 由引理7可知, 存在型為(3,2)3的(K4-e)-IGDD. 由引理11可知, 存在型為23的(K4-e)-GDND, 應用構(gòu)造3可得型為33的(K4-e)-GDND.

當n=4時, 令A=C, 區(qū)組為： {[0,3,5-6],[0,7,9-10],[1,3,4-10],[2,11,4-9],[3,8,2-9],[4,9,6-10],[5,7,2-4],[6,11,1-5],[7,8,1-6],[8,10,5-11]}. 令

可知(X,A)是帶余邊E4,1的型為34的(K4-e)-MGDP, (X,B)是帶超邊E1的型為34的(K4-e)-MGDC, 則(X,C)是型為34的(K4-e)-GDND.

當n∈{7,9,13}時, 由引理7可知, 存在型為(3,2)n的(K4-e)-IGDD. 由引理11可知, 存在型為2n的(K4-e)-GDND, 利用構(gòu)造3可得型為3n的(K4-e)-GDND. 當n∈{12,14}時, 由引理4可知, 存在型為3(n,4)的(K4-e)-IGDD. 已知存在型為34的(K4-e)-GDND, 利用構(gòu)造1可得型為3n的(K4-e)-GDND.

當n=8時, 令A=C, 區(qū)組為： {[0,2,1-3],[0,5,4-6],[0,9,7-10],[0,12,11-13],[0,15,14-17],[0,19,18-20],[0,22,21-23],[1,4,3-6],[1,7,5-8],[1,11,10-13],[1,14,12-16],[1,18,15-20],[19,22,1-2],[21,23,1-2],[2,7,4-6],[2,8,5-9],[2,14,11-13],[2,15,12-16],[17,20,2-3],[3,9,5-6],[3,10,7-8],[3,16,12-13],[14,21,3-4],[15,22,3-4],[18,23,3-4],[4,11,8-9],[4,13,10-17],[16,19,4-5],[5,12,10-17],[5,15,11-20],[14,23,5-8],[18,22,5-7],[6,13,8-15],[6,23,10-12],[6,18,11-16],[17,19,6-14],[20,21,6-11],[11,17,7-23],[7,21,12-16],[13,19,7-23],[14,20,7-10],[12,19,8-9],[15,21,8-9],[17,18,8-21],[20,22,8-13],[9,18,13-14],[16,22,9-11],[20,23,9-16],[10,19,15-21],[10,17,16-22]}. 令

可知(X,A)是帶余邊E2,1的型為38的(K4-e)-MGDP, (X,B)是帶超邊E3,3的型為38的(K4-e)-MGDC, 則(X,C)是型為38的(K4-e)-GDND.

引理13對于n∈{3,4,7,8,9,12,13,14}, 存在型為4n的(K4-e)-GDND.

證明: 令點集X=I4n, 組的集合為{{i,i+n,i+2n,i+3n}: 0≤i≤n-1}.

當n=3時, 令

可知(X,A)是帶余邊E3,1的型為43的(K4-e)-MGDP, (X,B)是帶超邊E2,1的型為43的(K4-e)-MGDC, 則(X,C)是型為43的(K4-e)-GDND.

當n=4時, 令A=C, 區(qū)組為： {[0,2,1-3],[0,6,5-7],[0,10,9-11],[0,14,13-15],[1,4,3-6],[1,8,7-10],[11,14,1-4],[12,15,1-2]，[2,7,4-13],[5,11,2-12],[8,9,2-11],[5,10,3-7],[6,13,3-11],[8,14,3-5],[9,12,3-6],[4,15,5-9],[10,13,4-12],[8,15,6-13],[7,14,9-12]}. 令

B=C∪{[10,15,9-12]}, E1={{10,15}}, E4,2={{9,10},{9,15},{10,12},{12,15}}.

可知(X,A)是帶余邊E1的型為44的(K4-e)-MGDP, (X,B)是帶超邊E4,2的型為44的(K4-e)-MGDC, 則(X,C)是型為44的(K4-e)-GDND.

當n∈{7,9,12,14}時, 由引理1、 引理2和引理4可知, 存在型為4(n,4)的(K4-e)-IGDD. 已知存在型為44的(K4-e)-GDND, 利用構(gòu)造1可得型為4n的(K4-e)-GDND. 當n=8時, 由引理2可知, 存在型為4(8,3)的(K4-e)-IGDD. 已知存在型為43的(K4-e)-GDND, 利用構(gòu)造1可得型為48的(K4-e)-GDND. 當n=13時, 由引理1可知, 存在型為4(13,8)的(K4-e)-IGDD. 已知存在型為48的(K4-e)-GDND, 利用構(gòu)造1可得型為413的(K4-e)-GDND.

引理14令g∈{1,2,3,4}, n≥3, 存在型為gn的(K4-e)-GDND.

證明: 對于g=1, 在Kn上討論.

當n≡0,1(mod5), n≥6時, 型為1n的(K4-e)-設(shè)計即為(K4-e)-GDND. 當n≡2,3,4(mod5), n≥8且n≠9時, 易知存在型為1n的(K4-e)-GDND[7-8]. 此時,

對于g∈{2,3,4}, 當n≡0,1(mod5)時, 型為g6的(K4-e)-GDD即為(K4-e)-GDND.

當n≡2,3,4(mod5), 3≤n≤14時, 由引理11～引理13知結(jié)論成立. 此時,

當(g,n)∈{(2,3),(3,3)}時,

2) g=6,7,8,9,11,12,13,14的情形.

引理15對于n≥3, 存在型為6n的(K4-e)-GDND.

證明: 當n≥3時, 由引理7可知, 存在型為(6,4)n的(K4-e)-IGDD. 由引理14可知, 存在型為4n的(K4-e)-GDND. 利用構(gòu)造3可得型為6n的(K4-e)-GDND.

引理16對于n≥3, 存在型為7n的(K4-e)-GDND.

證明: 令點集X=I7n, 組的集合為{{i,i+n,i+2n,i+3n,i+4n,i+5n,i+6n}: 0≤i≤n-1}.

當n=3時, 令A=C, 區(qū)組為： {[0,2,1-4],[0,7,5-8],[0,11,10-13],[0,16,14-17],[19,20,0-3],[1,5,3-6],[1,9,8-11],[1,14,12-15],[1,18,17-20],[2,10,3-12],[2,13,6-9],[2,18,7-19],[15,16,2-8],[3,14,4-7],[3,13,8-17],[11,16,3-18],[5,18,4-13],[4,11,6-15],[4,12,8-17],[9,20,4-7],[5,16,9-12],[5,15,10-19],[7,17,6-15],[6,19,8-14],[6,20,10-16],[11,12,7-19],[10,18,8-14],[9,17,10-19],[13,20,12-15]}. 令

可知(X,A)是帶余邊E2,1的型為73的(K4-e)-MGDP, (X,B)是帶超邊E3,3的型為73的(K4-e)-MGDC, 則(X,C)是型為73的(K4-e)-GDND.

當n=6時, 型為76的(K4-e)-GDD即為(K4-e)-GDND. 當n≥4, n≠6時, 由引理8可知, 存在型為(7,3)n的(K4-e)-IGDD. 由引理14可知, 存在型為3n的(K4-e)-GDND. 利用構(gòu)造3可得型為7n的(K4-e)-GDND.

引理17對于n≥3, 存在型為8n的(K4-e)-GDND.

證明: 令點集X=I8n, 組的集合為{{i,i+n,i+2n,i+3n,i+4n,i+5n,i+6n,i+7n}: 0≤i≤n-1}.

當n=3時, 令A=C, 區(qū)組為： {[0,2,1-4],[0,7,5-8],[0,11,10-13],[0,16,14-17],[19,20,0-3],[22,23,0-3],[1,5,3-6],[1,9,8-11],[1,14,12-15],[1,18,17-20],[21,23,1-4],[2,7,3-6],[2,10,9-15],[12,13,2-20],[2,18,16-22],[19,21,2-11],[4,14,3-6],[8,10,3-12],[11,16,3-12],[13,17,3-6],[5,9,4-19],[4,18,8-11],[12,17,4-7],[15,20,4-22],[10,18,5-23],[5,22,12-21],[5,15,13-16],[6,22,8-11],[6,20,10-16],[19,23,6-12],[7,20,9-21],[7,15,11-23],[14,18,7-19],[8,21,13-16],[15,19,8-17],[9,23,13-16],[9,22,14-17],[10,21,14-17]}. 令

B=C∪{[14,18,13-16]}, E2,1={{13,14},{13,18}}, E3,1={{14,16},{14,18},{16,18}}.

可知(X,A)是帶余邊E2,1的型為83的(K4-e)-MGDP, (X,B)是帶超邊E3,1的型為83的(K4-e)-MGDC, 則(X,C)是型為83的(K4-e)-GDND.

當n=6時, 型為86的(K4-e)-GDD即為(K4-e)-GDND. 當n≥4, n≠6時, 由引理9可知, 存在型為(8,3)n的(K4-e)-IGDD. 由引理14可知, 存在型為3n的(K4-e)-GDND. 利用構(gòu)造3可得型為8n的(K4-e)-GDND.

引理18對于n≥3, 存在型為9n的(K4-e)-GDND.

證明: 當n=6時, 型為96的(K4-e)-GDD即為(K4-e)-GDND. 當n≥3, n≠6時, 由引理9可知, 存在型為(9,4)n的(K4-e)-IGDD. 由引理14可知, 存在型為4n的(K4-e)-GDND. 利用構(gòu)造3可得型為9n的(K4-e)-GDND.

引理19對于n≥3, 存在型為11n的(K4-e)-GDND.

證明: 當n=4或n≥10時, 由引理8和引理14可知, 存在型為(11,1)n的(K4-e)-IGDD和型為1n的(K4-e)-GDND, 利用構(gòu)造3可得結(jié)論. 當n=5,6時, 型為11n的(K4-e)-GDD即為(K4-e)-GDND. 當n=3,7,9時, 由引理10和引理15可知, 存在型為(11,6)n的(K4-e)-IGDD和型為6n的(K4-e)-GDND, 利用構(gòu)造3可得結(jié)論. 當n=8時, 由引理3可知, 存在型為11(8,3)的(K4-e)-IGDD和型為113的(K4-e)-GDND, 利用構(gòu)造1可得結(jié)論.

引理20對于n≥3, g∈{12,14}, 存在型為gn的(K4-e)-GDND.

證明: 對于g∈{12,14}, 當n=6時, 型為g6的(K4-e)-GDD即為(K4-e)-GDND. 當n≥3, n≠6時, 令(g′,h′)∈{(6,4),(7,3)}, 由引理7和引理8可知, 存在型為(g′,h′)n的(K4-e)-IGDD. 由構(gòu)造4可知, 存在型為(2g′,2h′)n的(K4-e)-IGDD. 由引理15和引理17可知, 存在型為(2h′)n的(K4-e)-GDND. 利用構(gòu)造3可得型為gn的(K4-e)-GDND.

引理21對于n≥3, 存在型為13n的(K4-e)-GDND.

證明: 當n=6時, 型為136的(K4-e)-GDD即為(K4-e)-GDND. 當n≥3, n≠6時, 由引理8和引理16, 對于型為(13,7)n的(K4-e)-IGDD和型為7n的(K4-e)-GDND, 利用構(gòu)造3可得型為13n的(K4-e)-GDND.

3) 任意g的情形.

引理22對于n≥3, g≡1,2,3,4(mod5), g≥16, 存在型為gn的(K4-e)-GDND.

證明: 當n=6時, 型為g6的(K4-e)-GDD即為(K4-e)-GDND. 當n≥3, n≠6時, 令r∈{1,2,3,4}, g≡r(mod5). 由引理9可知, 存在型為(5+r,r)n的(K4-e)-IGDD, 則由引理6可得型為(g,5+r)n的(K4-e)-IGDD. 由引理15～引理18可知, 存在型為(5+r)n的(K4-e)-GDND, 利用構(gòu)造3可得結(jié)論.

綜上, 由引理14～引理22可得本文主要結(jié)果如下:

定理1對于n≥3, g≥1, 存在型為gn的(K4-e)-GDND, 且