2個(gè)七點(diǎn)七邊圖的圖填充與圖覆蓋設(shè)計(jì)

袁蘭黨, 楊立寶， 谷麗彥

(1.河北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，河北 石家莊 050024；2.邢臺(tái)學(xué)院 數(shù)學(xué)與信息技術(shù)學(xué)院，河北 邢臺(tái) 054001)

1 概念和主要結(jié)構(gòu)

設(shè)Kv是頂點(diǎn)集為X的v階完全圖.有限簡單圖G(=(V,E))的圖設(shè)計(jì)G-GDλ(v)是一個(gè)有序?qū)?X,B)，其中X是Kv的頂點(diǎn)集，B是Kv中一些與圖G同構(gòu)的子圖(稱為區(qū)組)的集合，使得Kv中的每條邊均恰好出現(xiàn)在B的λ個(gè)區(qū)組中.圖填充(或圖覆蓋)設(shè)計(jì)則是使得Kv中的每條邊至多(或至少)出現(xiàn)在B的λ個(gè)區(qū)組中.

圖設(shè)計(jì)是經(jīng)典的區(qū)組設(shè)計(jì)的推廣，并廣泛應(yīng)用于編碼、密碼和計(jì)算機(jī)科學(xué)中.關(guān)于圖設(shè)計(jì)的討論已有近30年的時(shí)間.圖填充與圖覆蓋設(shè)計(jì)是與圖設(shè)計(jì)平行的設(shè)計(jì)，就圖設(shè)計(jì)的存在譜之外的所有不小于圖G的邊數(shù)的正整數(shù)，證明了這些設(shè)計(jì)的存在性.其研究也已有一段歷史，主要涉及的是存在圖設(shè)計(jì)的圖類，如五點(diǎn)以下的完全圖、六點(diǎn)七邊圖和一部分六點(diǎn)九邊圖等[1-3].易見,G-GDλ(v)存在的必要條件為

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

(1)

這里d是V中各頂點(diǎn)的度的最大公因數(shù).

對于一個(gè)v階圖填充(或圖覆蓋)設(shè)計(jì)，如果不存在其他同階數(shù)的圖填充(或圖覆蓋)設(shè)計(jì)含有更多(或更少)的區(qū)組，則稱其為最大(或最小)的，記為maxG-PDλ(v)(X,P)(或minG-CDλ(v)(X,C))，其余邊圖(或重邊圖)記為Lλ(或Rλ)，并稱余邊圖(或重邊圖)的邊數(shù)為余邊數(shù)(或重邊數(shù))，記為lλ(或rλ).此時(shí)稱區(qū)組數(shù)|P|(或|C|)為填充數(shù)p(v,G,λ)(或覆蓋數(shù)c(v,G,λ).顯然,

其中|E|表示圖G的邊數(shù)，?x?(或「x?)表示不超過(或不小于)x的最大(或最小)整數(shù).若填充數(shù)(或覆蓋數(shù))使得左邊(或右邊)等號(hào)成立，則稱該最大圖填充(或最小圖覆蓋)設(shè)計(jì)為正則的，記為G-OPDλ(v)(或G-OCDλ(v)).

引理1[1]對圖G和正整數(shù)v,λ,u,

1)若存在G-OPDλ(v)，且余邊圖Lλ?G,則存在G-OCDλ(v)，其重邊圖為GLλ;

2)若存在G-OPDλ(v)和G-OPDμ(v)，其區(qū)組集分別為P和P′，余邊圖為Lλ和Lμ，如果lλ+lμ=lλ+μ，則存在G-OPDλ+μ(v)，其區(qū)組集為P∪P′，余邊圖為Lλ∪Lμ；

3)若存在G-OPDλ(v)和G-OCDμ(v)，其區(qū)組集分別為P和C，余邊圖和重邊圖分別為Lλ和Rμ，如果Lλ?Rμ且lλ-rμ=lλ+μ，則存在G-OPDλ+μ(v)，其區(qū)組集為P∪C，余邊圖為LλRμ.

本文中，筆者研究如下2個(gè)含C5的七點(diǎn)七邊圖D1，D2，其頂點(diǎn)標(biāo)記為(a,b,c,d,e,f,g).

圖1 2個(gè)七點(diǎn)七邊圖

由1)，Di-GDλ(v)(i=1,2)存在的必要條件為λv(v-1)≡0(mod 14),v≥7，即當(dāng)λ?0(mod 7)時(shí)，v≡0,1(mod 7);當(dāng)λ≡0(mod 7)時(shí)，v≥7.

文獻(xiàn)[4]已證明圖設(shè)計(jì)Di-GDλ(v)(i=1,2)存在的必要條件也是充分的，從而給出了圖設(shè)計(jì)的存在譜.

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

由定義，圖設(shè)計(jì)既是正則圖填充設(shè)計(jì)，也是正則圖覆蓋設(shè)計(jì)，以下對圖設(shè)計(jì)的存在譜以外的正整數(shù)v≥7，證明正則圖填充和正則圖覆蓋設(shè)計(jì)的存在性.

文獻(xiàn)[4]給出了有限簡單圖G的帶洞圖設(shè)計(jì)和不完全圖設(shè)計(jì)的概念.圖G的帶洞圖設(shè)計(jì)G-HD(nt)是完全多部圖Kn,n…,n的邊分解A(稱為區(qū)組集)，其中A中的元素(稱為區(qū)組)是Kn,n…,n的子圖且與G同構(gòu).特殊地，若完全(v+1)部圖K1,1，…,1，w亦可分拆為與G同構(gòu)的圖，則稱其為不完全圖設(shè)計(jì)，記為G-ID(v+w,w)，且有以下引理.

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

利用帶洞圖設(shè)計(jì)和不完全圖設(shè)計(jì)可以給出圖填充和圖覆蓋設(shè)計(jì)的遞歸構(gòu)造.

定理2[2]對于圖G及正整數(shù)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，設(shè)λ=λ0是使得G-GDλ(v)存在的最小正整數(shù)，若對1≤s≤λ0-1,G-OPDs(v)和G-OCDs(v)存在，則對任意正整數(shù)λ，G-OPDλ(v)和G-OCDλ(v)也存在.

由定理1和3，只需構(gòu)作以下圖填充Di-OPDλ(v)與圖覆蓋Di-OCDλ(v),i=1,2:

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

(2)

2 λ=1時(shí)的圖填充和圖覆蓋

注 當(dāng)λ=1時(shí)，各類設(shè)計(jì)符號(hào)中的下標(biāo)λ可省略.

表1 λ=1時(shí)的余邊數(shù)和重邊數(shù)

以下構(gòu)作的Di-OPD(v)(i=1,2)均滿足引理1的條件1)，因此可直接得到相應(yīng)的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)}.

注 以下的區(qū)組中，所涉及到的加法運(yùn)算在相應(yīng)的循環(huán)群Zv中進(jìn)行.

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.

當(dāng)t=1,2時(shí)，由引理3知，結(jié)論成立.

當(dāng)t≥3時(shí)，由引理2和3知，存在Di-HD(7t),t≥3和Di-ID(7+w,w),Di-OPD(7+w)，Di-OCD(7+w),2≤w≤6,再由定理2，結(jié)論成立.

3 λ>1時(shí)的圖填充和圖覆蓋

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

表2 λ≥1,w=2,6時(shí)的余邊數(shù)和重邊數(shù)表

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

證由(2)可知，僅需對1≤λ≤6構(gòu)作.如表3所示.

表3 λ≥1,w=3,5時(shí)的余邊數(shù)和重邊數(shù)

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

證由(2)可知，僅需對1≤λ≤6構(gòu)作.如表4所示.

表4 λ≥1,w=4時(shí)的余邊數(shù)和重邊數(shù)

至此，由定理1和引理4～6，可得以下主要結(jié)論:

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