七點七邊圖的圖分解

袁蘭黨,楊立保,谷麗彥,白占立

(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).

3 結論

至此,已構造出引理1中所需的各類圖分解,這樣,就得到了以下結論,即所討論的圖分解的存在譜:

定理1對于1≤i≤2,Di-GDλ(v)存在的充分必要條件為λv(v-1)≡0(mod 14),v≥7.