2个七点七边图的图填充与图覆盖设计

袁兰党, 杨立宝， 谷丽彦

(1.河北师范大学 数学科学学院，河北 石家庄 050024；
2.邢台学院 数学与信息技术学院，河北 邢台 054001)

设Kv是顶点集为X的v阶完全图.有限简单图G(=(V,E))的图设计G-GDλ(v)是一个有序对(X,B)，其中X是Kv的顶点集，B是Kv中一些与图G同构的子图(称为区组)的集合，使得Kv中的每条边均恰好出现在B的λ个区组中.图填充(或图覆盖)设计则是使得Kv中的每条边至多(或至少)出现在B的λ个区组中.

图设计是经典的区组设计的推广，并广泛应用于编码、密码和计算机科学中.关于图设计的讨论已有近30年的时间.图填充与图覆盖设计是与图设计平行的设计，就图设计的存在谱之外的所有不小于图G的边数的正整数，证明了这些设计的存在性.其研究也已有一段历史，主要涉及的是存在图设计的图类，如五点以下的完全图、六点七边图和一部分六点九边图等[1-3].易见,G-GDλ(v)存在的必要条件为

v≥|V|,λv(v-1)≡0(mod 2|E|),λ(v-1)≡0(modd),

(1)

这里d是V中各顶点的度的最大公因数.

对于一个v阶图填充(或图覆盖)设计，如果不存在其他同阶数的图填充(或图覆盖)设计含有更多(或更少)的区组，则称其为最大(或最小)的，记为maxG-PDλ(v)(X,P)(或minG-CDλ(v)(X,C))，其余边图(或重边图)记为Lλ(或Rλ)，并称余边图(或重边图)的边数为余边数(或重边数)，记为lλ(或rλ).此时称区组数|P|(或|C|)为填充数p(v,G,λ)(或覆盖数c(v,G,λ).显然,

其中|E|表示图G的边数，⎣x⎤(或「x⎤)表示不超过(或不小于)x的最大(或最小)整数.若填充数(或覆盖数)使得左边(或右边)等号成立，则称该最大图填充(或最小图覆盖)设计为正则的，记为G-OPDλ(v)(或G-OCDλ(v)).

引理1[1]对图G和正整数v,λ,u,

1)若存在G-OPDλ(v)，且余边图Lλ⊂G,则存在G-OCDλ(v)，其重边图为GLλ;

2)若存在G-OPDλ(v)和G-OPDμ(v)，其区组集分别为P和P′，余边图为Lλ和Lμ，如果lλ+lμ=lλ+μ，则存在G-OPDλ+μ(v)，其区组集为P∪P′，余边图为Lλ∪Lμ；

3)若存在G-OPDλ(v)和G-OCDμ(v)，其区组集分别为P和C，余边图和重边图分别为Lλ和Rμ，如果Lλ⊃Rμ且lλ-rμ=lλ+μ，则存在G-OPDλ+μ(v)，其区组集为P∪C，余边图为LλRμ.

本文中，笔者研究如下2个含C5的七点七边图D1，D2，其顶点标记为(a,b,c,d,e,f,g).

图1 2个七点七边图

由1)，Di-GDλ(v)(i=1,2)存在的必要条件为λv(v-1)≡0(mod 14),v≥7，即当λ≢0(mod 7)时，v≡0,1(mod 7);当λ≡0(mod 7)时，v≥7.

文献[4]已证明图设计Di-GDλ(v)(i=1,2)存在的必要条件也是充分的，从而给出了图设计的存在谱.

定理1Di-GDλ(v)(i=1,2)存在的充分必要条件为λv(v-1)≡0(mod14),v≥7.

由定义，图设计既是正则图填充设计，也是正则图覆盖设计，以下对图设计的存在谱以外的正整数v≥7，证明正则图填充和正则图覆盖设计的存在性.

文献[4]给出了有限简单图G的带洞图设计和不完全图设计的概念.图G的带洞图设计G-HD(nt)是完全多部图Kn,n…,n的边分解A(称为区组集)，其中A中的元素(称为区组)是Kn,n…,n的子图且与G同构.特殊地，若完全(v+1)部图K1,1，…,1，w亦可分拆为与G同构的图，则称其为不完全图设计，记为G-ID(v+w,w)，且有以下引理.

引理2[4]存在Di-HD(7t)(t≥3)和Di-ID(7+w,w)(2≤w≤6),i=1,2.

利用带洞图设计和不完全图设计可以给出图填充和图覆盖设计的递归构造.

定理2[2]对于图G及正整数h,w,λ,t(t≥3).若存在G-HD(ht),G-ID(h+w,w)和G-OPDλ(h+w)(或G-OCDλ(h+w))，则存在G-OPDλ(th+w)(或G-OCDλ(th+w))，且它的余边图(或重边图)与前者一致.

定理3[3]对给定的v，设λ=λ0是使得G-GDλ(v)存在的最小正整数，若对1≤s≤λ0-1,G-OPDs(v)和G-OCDs(v)存在，则对任意正整数λ，G-OPDλ(v)和G-OCDλ(v)也存在.

由定理1和3，只需构作以下图填充Di-OPDλ(v)与图覆盖Di-OCDλ(v),i=1,2:

v=2,3,4,5,6(mod 7)且v≥7,1≤λ≤6(此时λ0=7).

(2)

注 当λ=1时，各类设计符号中的下标λ可省略.

表1 λ=1时的余边数和重边数

以下构作的Di-OPD(v)(i=1,2)均满足引理1的条件1)，因此可直接得到相应的Di-OCD(v),下面不再赘述.

引理3对于1≤i≤2，存在Di-OPD(v)和Di-OCD(v),v=7t+w,t=1,2,2≤w≤6.

证1)由引理2知，存在Di-ID(9,2)，即为Di-OPD(9).

2)v=10,X=Z10.

D1:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,3,7,6,4,1),(0,8,1,7,9,2,5),(6,2,9,3,8,7,4),(6,5,7,4,9,8,1),L1={(0,7),(7,8),(8,9)};

D2:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,1,7,6,8,2),(0,8,5,6,9,3,2),(6,4,9,3,8,5,7),(8,2,9,7,4,1,5),L2={(0,7),(7,8),(8,9)}.

3)v=11,X=Z11.

D1:(0,8,3,2,7,5,1),(5,9,4,1,10,3,0),(4,6,7,3,10,8,2),(0,2,5,1,9,8,10),(0,4,8,9,6,5,3),(7,5,3,1,8,0,10),(10,6,2,9,7,5,4),L1={(0,1),(0,3),(1,2),(1,6),(2,4),(3,4)};

D2:(6,1,7,2,8,0,9),(5,0,10,3,9,1,8),(1,4,10,6,9,2,7),(0,2,4,5,3,6,1),(1,3,6,0,8,2,9),(8,9,7,5,10,4,6),(9,4,8,7,10,5,3),L2={(0,1),(0,4),(1,2),(2,3),(2,5),(3,4)}.

4)v=12,X=Z12.

D1:(0,8,4,1,7,3,2),(5,10,4,2,9,3,0),(3,7,5,6,11,4,0),(1,9,4,0,10,3,2),(0,2,5,1,3,6,4),(0,5,8,1,6,3,7),(2,8,7,9,11,10,1),(6,4,11,10,9,5,8),(8,6,10,7,11,3,5),L1={(0,1),(1,2),(2,3)};

D2:(6,0,7,2,8,1,9),(0,5,10,3,11,4,9),(0,4,11,6,10,2,9),(5,1,8,0,9,3,2),(1,3,2,5,4,6,7),(1,6,3,4,9,0,7),(5,3,7,10,8,6,11),(6,4,8,11,5,7,9),(11,1,10,9,7,2,8),L2={(0,1),(1,2),(2,4)}.

5)v=13,X=Z13.

D1:(6,7,3,1,8,2,0),(5,9,1,2,10,0,4),(2,11,3,4,12,0,6),(4,7,5,6,9,1,2),(5,8,4,1,12,3,0),(0,1,5,2,3,6,9),(0,2,4,6,10,8,1),(0,4,5,3,6,11,2),(3,10,7,11,12,8,9),(8,7,0,5,11,9,1),(10,11,9,8,12,6,7),L1={(9,10)};

D2:(0,3,7,2,8,1,9),(4,5,10,2,11,3,12),(8,1,9,5,6,3,11),(5,0,12,3,8,6,11),(0,1,2,3,4,5,6),(0,2,4,1,6,7,3),(0,7,5,1,10,3,11),(0,9,4,6,11,8,2),(4,10,6,7,12,9,8),(8,9,10,12,11,7,1),(10,8,12,9,11,5,7),L2={(7,11)}.

注 以下的区组中，所涉及到的加法运算在相应的循环群Zv中进行.

6)v=16,X=Z15∪{∞}.

D1:(0,1,4,7,10,8,5),(2,5,8,13,7,14,∞),(6,3,8,4,9,0,1),(9,7,12,1,14,8,2),(2+i,i,∞,8+i,9+i,6+i,5+i),(2+j,j,3+j,8+j,9+j,6+j,5+j),0≤i≤6,8≤j≤13,L1={(6,11)};

D2:(0,5,3,6,11,2,1),(2,6,9,4,7,12,14),(5,8,11,4,13,14,2),(11,10,7,3,13,∞,8),(∞,i,6+i,4+i,8+i,13+i,3+i),(5+j,j,6+j,4+j,8+j,13+j,3+j),(13,7,12,5,10,0,14),0≤i≤6,8≤j≤12,L2={(1,2)}.

7)v=17,X=Z15∪{a,b}.

D1:(0,1,6,5,10,2,11),(2,0,5,4,8,14,3),(4,3,13,8,9,2,10),(4,7,12,13,14,0,9),(12,2,7,6,11,b,1),(i,7+i,4+i,8+i,2+i,a,b),1≤i≤14,L1={(7,8),(7,a),(a,b)};

D2:(0,2,1,6,5,3,7),(0,7,4,5,10,14,9),(3,2,7,8,4,12,5),(3,13,12,2,b,11,8),(8,3,9,14,13,4,0),(9,8,1,11,10,a,6),(4+i,7+i,i,2+i,8+i,a,b),2≤i≤14,L2={(0,1),(0,a),(a,b)}.

8)v=18,X=Z17∪{∞}.

D1:(1,4,7,5,12,8,11),(2,7,12,4,13,1,8),(9,4,14,3,6,15,11),(9,8,5,16,10,11,7),(15,14,13,12,16,9,∞),(11,10,5,2,16,15,14),(6+i,13+i,i,∞,8+i,5+i,2+i),(6+j,13+j,j,3+j,8+j,5+j,7+j),0≤i≤7,9≤j≤15,L1={(0,3),(0,6),(0,11),(3,8),(6,7),(7,8)};

D2:(1,4,7,5,12,2,8),(2,5,10,11,16,7,0),(4,8,11,6,9,12,3),(4,14,16,10,15,∞,9),(15,14,13,12,16,2,7),(8,9,14,5,13,3,16),(i,13+i,6+i,8+i,∞,14+i,2+i),(j,13+j,6+j,8+j,3+j,14+j,7+j),0≤i≤7,9≤j≤15,L2={(0,3),(0,6),(1,7),(3,8),(6,7),(7,8)}.

9)v=19,X=Z19.

D1:(10,2,5,18,8,13,16),(16,14,12,10,18,3,7),(17,0,8,4,15,11,13),(0,2,1,3,5,4,16),(8,1,12,4,6,18,14),(9,7,5,13,11,15,3),(i,6+i,3+i,2+i,9+i,1+i,5+i),0≤i≤17,L1={(1,9),(6,17),(9,17)};

D2:(2,13,5,18,10,3,7),(4,15,7,5,2,9,16),(18,16,14,3,1,12,11),(17,6,4,8,0,12,18),(15,17,9,11,13,1,0),(12,10,8,6,1,16,14),(6+i,3+i,2+i,9+i,i,7+i,5+i),0≤i≤17,L2={(0,2),(1,2),(1,8)}.

10)v=20,X=Z20.

D1:(0,4,10,16,3,1,9),(0,6,7,1,5,12,11),(5,18,7,8,15,12,9),(19,9,2,15,1,16,11),(0,18,8,19,13,4,3),(4,19,7,17,11,5,18),(0,8,1,14,7,2,13),(0,14,4,17,10,8,3),(19,12,2,16,6,5,13),(i,2+i,6+i,1+i,9+i,5+i,8+i),0≤i≤17,L1={(3,17)};

D2:(0,8,5,13,3,1,10),(0,12,2,7,10,5,4),(15,12,9,17,5,19,0),(17,14,6,18,7,19,8),(1,18,4,16,13,12,8),(6,16,19,8,7,2,11),(1,6,2,14,4,10,11),(1,11,3,6,9,5,4),(19,7,15,18,5,3,10),(8+i,3+i,7+i,i,9+i,5+i,6+i),0≤i≤17,L2={(11,19)}.

定理4对于1≤i≤2，存在Di-OPD(v)和Di-OCD(v),v≡2,3,4,5,6(mod 7)，v≥7.

证令v=7t+w,2≤w≤6,t≥1.

当t=1,2时，由引理3知，结论成立.

当t≥3时，由引理2和3知，存在Di-HD(7t),t≥3和Di-ID(7+w,w),Di-OPD(7+w)，Di-OCD(7+w),2≤w≤6,再由定理2，结论成立.

引理4对于1≤i≤2,λ≥1，存在Di-OPDλ(v)和Di-OCDλ(v),v≡2,6(mod 7),v≥9.

表2 λ≥1,w=2,6时的余边数和重边数表

引理5对1≤i≤2,λ≥1，存在Di-OPDλ(v)和Di-OCDλ(v),v≡3,5～(mod 7),v≥10.

证由(2)可知，仅需对1≤λ≤6构作.如表3所示.

表3 λ≥1,w=3,5时的余边数和重边数

引理6对1≤i≤2,λ≥1，存在Di-OPDλ(v)和Di-OCDλ(v),v≡4(mod 7),v≥11.

证由(2)可知，仅需对1≤λ≤6构作.如表4所示.

表4 λ≥1,w=4时的余边数和重边数

至此，由定理1和引理4～6，可得以下主要结论:

定理5对任意的v≥7，存在Di-OPDλ(v)和Di-OCDλ(v),λ≥1,i=1,2.