七点七边图的图分解

2021-08-19袁兰党杨立保谷丽彦白占立

河北大学学报（自然科学版） 2021年4期

袁兰党,杨立保,谷丽彦,白占立

(1.河北师范大学数学科学学院,河北省数学研究中心，河北石家庄 050024；2.邢台学院数学科学技术学院,河北邢台 054001；3.河北师范大学学报编辑部,河北石家庄 050024)

1 概念和主要结构

组合设计是组合数学中的一个重要分支,主要研究满足不同条件的构造的存在性,广泛应用于计算机科学、编码密码中.图分解是传统的区组设计的推广,是将区组设计中完全图推广到有限简单图,其内容更加丰富,应用范围也更广泛.关于图分解的研究有几十年了,代表性文章参见文献[1-6]，其中分别给出了星图K1,k、圈图Cn和六点八边图的图分解存在谱.本文旨在研究2个七点七边图的图分解,是将多重完全图分解为若干个两两不相交且同构的七点七边图的并,确定图分解的存在谱.先介绍相关的基本概念[5]和主要结构.

设λKv是顶点集为X的v阶λ重完全图.有限简单图G=(V,E)的图分解是图λKv的边分解B(称为区组集),其中B中的元素是Kv的子图且与G同构.该图分解记为G-GDλ(v)=(X,B).显然,G-GDλ(v)存在的必要条件为

v≥|V(G)|,λv(v-1)≡0(mod2|E|),λ(v-1)≡0(modd),

(1)

其中，d是V中各顶点的度的最大公因数.

有限简单图G的带洞图分解是图λKn,n,…,n的边分解A(称为区组集),其中A中的元素称为区组是Kn,n,…,n的子图且与G同构.该带洞图分解记为G-HD(nt)=(X,H,A),其中H={Xi|i=1,2,…,t}为洞集合.特殊地,若λ重完全(v+1)部图λK1,1,…,1,w亦可拆分为与G同构的图,则称其为洞长为w的不完全G-分解,记为G-IDλ(v+w,w).易见,G-GDλ(v+1)为G-IDλ(v+1,1).当λ=1时,以上记号中的下标λ通常省略.

本文研究2个含C5的七点七边图Di(1≤i≤2)的图分解(图1，图2)，这些图的顶点标记为(a,b,c,d,e,f,g).

图1 七点七边图D1Fig.1 Graph with seven vertices and seven edges D1

图2 七点七边图D2Fig 2.Graph with seven vertices and seven edges D2

由式(1),对于1≤i≤2,Di-GDλ(v)存在的必要条件为λv(v-1)≡0(mod 14),v≥7,即当λ≡1,2,3,4,5,6(mod 7)时,v≡0,1(mod 7);当λ≡0(mod 7)时,v≥7.

将证明图分解Di-GDλ(v)(1≤i≤2)存在的必要条件也是充分的,从而给出图分解的存在谱.易见,对任意λ,μ∈Z+,若G-GDλ(v)存在,则G-GDλμ(v)存在.因此,只需分别讨论λ=1,7的情形.

引理1[5]设G是有限简单图,h、t、λ是正整数,w≥0.若存在G-HDλ(ht),G-IDλ(h+w,w)和G-GDλ(h+w),则存在G-GDλ(th+w).

2 HDs、IDs和GDs的构造

图分解是经典的区组设计的推广,区组设计中常用的差方法可以推广应用于图分解的构造.

设X是v阶可交换群,G=(S,E)为有限简单图,点集S是集合X的子集合,λ为给定的正整数,若X中任意一个非零元g,都有λ个序对x,y∈S,{x,y}∈E,使得g=x-y,则称G为Abel群X的一个(v,G,λ)-差图.特别地,当X是循环群时,则称G为群X的一个(v,G,λ)-循环差图.进一步,对a∈X,定义G的一个平移G+a={x+a|x∈S},又令DevG={G+a|a∈X},则(X,DevG)为图分解G-GDλ(v).

设X是v阶可交换群,G为有限简单图,设s是正整数.再设S是由s个与图G同构的图G1,G2,…,Gs组成的图族,这里,Gi=(Si,Ei),Si⊆X,i=1,2,…,s,若X中任意非零元g都恰有λ次表成如下形式的差:g=bij-bil,1≤i≤s,bij,bil∈Si,{bij,bil}∈Ei,i=1,2,…,s，则称S为群X的一个(v,G,λ)-差图族.特别地,当X是循环群时,则称S为群X的一个(v,G,λ)-循环差图族.进一步,对a∈X,定义G的一个平移Gi+a={x+a|x∈Si},进而令DevS={Gi+a|i=1,2,…,s,a∈X},则(X,DevS)为图分解G-GDλ(v).

类似地,差图或差图族亦可用来构造带洞图分解和不完全图分解.

在本文中,构作各类图分解时用到的集合Zv通常为v阶循环群,并记DevS:=Smodv.

例:对于图D1来说,B:(0,4,9,3,1,7,8)mod 15即为集合Z15上D1-GD(15)的区组集.

引理2对于1≤i≤2,存在Di-HD(7t),t≥3.

因此,只需构作Di-HD(7k),k∈{3,4,5,6,8},便可得到Di-HD(7t),t≥3.

k=3:X=Z21,H={{3j+i:j∈Z7}|i∈Z3},mod 21.

D1:(20,1,17,4,0,8,10);D2:(17,1,20,0,4,13,10).

k=4:X=Z7×(Z3∪{∞}),H={Z7×{x}|x∈Z3∪{∞}},mod(7,3).

D1:(00,42,01,12,1∞,2∞,20),(40,41,62,50,1∞,22,61);

D2:(01,42,00,1∞,12,5∞,20),(41,62,50,1∞,40,31,61).

k=5:X=Z35,H={{5j+i:j∈Z7}|i∈Z5},mod 35.

D1:(1,27,16,12,0,20,3),(16,30,8,2,0,13,27);

D2:(16,27,1,0,12,8,3),(30,8,2,0,16,19,27).

k=6:X=Z7×(Z5∪{∞}),H={Z7×{x}|x∈Z5∪{∞}},mod(7,5).

D1:(01,22,44,62,00,6∞,43),(63,00,52,01,1∞,41,10),(24,63,60,54,1∞,02,30);

D2:(62,00,01,22,44,33,6∞),(52,00,63,1∞,01,22,10),(60,63,24,1∞,54,10,30).

k=8:X=Z7×(Z7∪{∞}),H={Z7×{x}|x∈Z7∪{∞}},mod(7,7).

D1:(00,63,12,54,1∞,42,65),(12,34,45,1∞,10,05,53),(12,11,35,1∞,20,34,53),
(56,44,31,22,53,62,21);

D2:(12,54,1∞,00,63,65,21),(45,34,12,10,1∞,41,53),(1∞,20,12,11,35,45,34),
(44,56,53,22,31,21,04).

引理3对于i=1,2,存在Di-GD(v),v=7,8,14,15.

证明:v=7,X=(Z3×Z2)∪{∞},mod(3,-),

D1:(∞,00,01,10,21,20,11);D2:(∞,20,21,00,11,01,10).

v=8,X=Z8,

D1:(0,1,2,3,4,5,6),(0,2,4,1,6,5,7),(1,3,0,5,7,6,4),(3,5,6,2,7,4,0);

D2:(0,1,2,3,4,5,6),(0,2,4,1,6,7,5),(3,0,5,7,1,6,2),(5,3,7,6,4,0,2)

v=14,X=Z13∪{∞},mod 13，

D1:(0,4,9,3,1,7,∞);D2:(0,4,9,3,1,6,∞).

v=15,X=Z15,mod 15,

D1:(0,4,9,3,1,7,8);D2:(0,4,9,3,1,6,10).

引理4对于1≤i≤2,存在Di-GD7(v),v=7k+w,k=1,2,2≤w≤6.

证明:v=9,X=Z9,mod 9,

D1:(0,1,3,6,4,2,7)×3,(4,8,7,3,0,6,5);D2:(0,1,3,7,6,5,4)×3,(7,8,4,0,3,6,5).

v=10,X=Z9∪{∞},mod 9,

D1:(∞,0,4,3,1,6,5)×3,(0,1,3,5,2,∞,8),(0,1,2,5,3,6,4);

D2:(∞,0,4,3,1,7,8)×3,(2,0,1,3,5,∞,6),(0,1,2,5,3,6,4).

v=11,X=Z11,mod 11,

D1:(0,1,3,6,2,4,7)×3,(0,1,5,4,9,8,10),(0,4,8,3,10,7,5);

D2:(0,1,3,6,2,8,9)×3,(1,5,4,9,0,3,2),(0,4,8,3,10,5,9).

v=12,X=Z11∪{∞},mod 11,

D1:(∞,0,4,2,1,3,6)×3,(0,1,3,6,7,∞,2),(0,2,5,1,6,7,3),(0,1,5,3,4,10,7);

D2:(∞,0,4,2,1,7,8)×3,(0,1,3,6,7,8,∞),(0,2,5,1,6,8,7),(0,1,5,3,4,7,6).

v=13,X=Z13,mod 13,

D1:(0,1,3,6,7,5,2)×3,(0,2,5,1,6,4,3),(0,4,9,3,6,8,1),(0,2,1,3,6,7,10);

D2:(0,1,3,6,7,8,2)×3,(0,2,5,1,6,3,4),(0,4,9,3,6,5,8),(0,2,1,3,6,5,8).

v=16,X=Z15∪{∞},mod 15,

D1:(0,1,3,10,4,6,7)×4,(∞,0,4,2,1,7,6)×2,(∞,0,3,9,1,6,4),(0,1,3,6,10,∞,4);

D2:(0,1,3,10,4,8,7)×4,(∞,0,4,2,1,11,7)×2,(∞,10,3,9,12,6,0),(0,1,3,6,10,9,∞).

v=17,X=Z17,mod 17,

D1:(0,1,3,10,4,6,7)×6,(0,8,1,9,3,16,11),(0,8,3,11,2,4,1);

D2:(0,1,3,10,4,8,7)×6,(0,8,1,9,3,10,5),(0,8,3,11,2,12,10).

v=18,X=Z17∪{∞},mod 17,

D1:(0,1,3,6,10,∞,2)×5,(∞,0,5,7,1,6,13),(0,5,10,12,6,11,1),
(0,1,4,12,5,7,9)×2;

D2:(0,1,3,6,10,11,∞)×5,(∞,0,5,7,1,11,12),(0,5,10,12,6,4,7),
(0,1,4,12,5,10,8)×2.

v=19,X=Z19,mod 19,

D1:(0,1,3,6,10,7,5)×6,(0,7,14,16,8,15,1),(0,7,14,6,13,15,5),(0,1,4,13,5,8,9);

D2:(0,1,3,6,10,9,11)×6,(0,7,14,16,8,6,9),(0,7,14,6,13,3,17),(0,1,4,13,5,11,9).

v=20,X=Z19∪{∞},mod 19,

D1:(∞,0,5,11,1,6,8),(0,1,3,6,10,∞,2)×5,(0,5,11,4,12,1,9)×2,
(0,5,10,4,9,6,3),(0,2,9,8,6,7,13);

D2:(∞,0,5,11,1,12,17),(0,1,3,6,10,∞,14)×5,(0,5,11,4,12,7,1)×2,
(0,5,10,4,9,11,17),(0,2,9,8,6,4,1).

引理5对于1≤i≤2,存在Di-ID(7+w,w),2≤w≤6.

证明:取X=Z7+w,洞为{7+i|i∈Zw},2≤w≤6.

w=2:

D1:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,3,7,6,8,1),(0,7,2,6,8,4,3),(4,5,7,1,8,6,2);

D2:(0,1,2,3,4,5,6),(0,2,4,1,3,5,6),(0,5,1,7,6,8,2),(3,5,8,4,7,2,6),(7,0,8,6,5,3,2).

w=3:

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

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

w=4:

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

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

w=5:

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,1,2,3,6,5,7),(0,2,11,4,5,8,3),(2,5,11,1,6,8,9),(4,3,1,8,6,0,10);

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),
(0,1,2,4,3,5,7),(1,6,7,5,11,3,8),(9,1,3,5,4,2,6),(10,1,4,6,2,8,3).

w=6:

D1:(6,7,3,1,8,2,0),(5,9,12,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,11,9),(4,010,1,6,2,3),(6,0,5,4,2,7,8),
(5,3,10,6,11,12,4);

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),
(1,6,7,0,10,4,11),(0,1,2,4,6,3,8),(6,2,5,1,11,7,3),(6,9,0,4,10,2,12),
(12,1,4,3,5,9,6).