雙凱萊圖的完全完備碼

李建勛,王 燕

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,山東 煙臺(tái) 264005)

完備碼(圖論中也稱為有效控制集)問(wèn)題是基于圖中頂點(diǎn)集合劃分提出的,目的是利用圖中的孤立點(diǎn)集將所有頂點(diǎn)進(jìn)行劃分。這種劃分也是圖模擬網(wǎng)絡(luò)進(jìn)行穩(wěn)定性研究的一個(gè)重要方面。而完全完備碼是利用圖中的匹配來(lái)代替孤立點(diǎn)集來(lái)劃分圖的頂點(diǎn)集合,這樣也增加了網(wǎng)絡(luò)的穩(wěn)定性。

定義1假定Γ是一個(gè)圖,T是頂點(diǎn)集V(Γ)的一個(gè)子集。若Γ的每一個(gè)點(diǎn)都與T中的唯一的一個(gè)點(diǎn)相鄰,則稱T是Γ的一個(gè)完全完備碼。

由定義可知,T中每一個(gè)點(diǎn)也恰好和它內(nèi)部的一個(gè)點(diǎn)相鄰,因而T是一個(gè)匹配。近些年來(lái),點(diǎn)傳遞圖尤其是凱萊圖中的完全完備碼問(wèn)題受到了廣泛關(guān)注。例如文獻(xiàn)[1]刻畫了二部凱萊圖的完全完備碼,并給出了某些循環(huán)Harary圖存在完全完備碼的充要條件。文獻(xiàn)[2]給出了有限群的一個(gè)共軛封閉子集構(gòu)成該群的凱萊圖的完全完備碼的充要條件。文獻(xiàn)[3]給出了完備碼個(gè)數(shù)為2的方冪的循環(huán)圖存在完全完備碼的充要條件以及給出了子群可作為完全完備碼的一個(gè)充要條件。文獻(xiàn)[4]刻畫了奇素?cái)?shù)度循環(huán)圖中存在完全完備碼的充要條件。文獻(xiàn)[5]討論了循環(huán)群上4度凱萊圖的完全完備碼問(wèn)題。關(guān)于交換群上的凱萊圖,文獻(xiàn)[6]給出了交換群上4度凱萊圖存在完全完備碼的充要條件。

本研究關(guān)注雙凱萊圖完全完備碼的存在性問(wèn)題。一般來(lái)說(shuō),雙凱萊圖不是點(diǎn)傳遞圖,但是它是最接近點(diǎn)傳遞圖的一類圖。

定義2設(shè)H是一個(gè)有限群,R,L,S是H的子集合,滿足1?R∪L,R=R-1,L=L-1。定義H關(guān)于R,L,S的雙凱萊圖,記作Γ=BiCay(H;R,L,S)。其中Γ的點(diǎn)集合V(Γ)=H0∪H1,Hi={hi|h∈H},i=0,1,邊集合E(Γ)={{h0,(xh)0},{h1,(yh)1},{h0,(zh)1}︳x∈R,y∈L,z∈S}。特別地,如果R=L=?,則稱Γ是一個(gè)Haar圖,關(guān)于Haar圖,可以參考文獻(xiàn)[7]。

第1節(jié),列出了雙凱萊圖及完全完備碼的一些基本性質(zhì)。第2節(jié)給出了正則雙凱萊圖的一個(gè)頂點(diǎn)子集合是完全完備碼的幾個(gè)等價(jià)條件。作為第2節(jié)主要結(jié)果的應(yīng)用,第3節(jié)考慮了一些特殊的完全完備碼。

1 預(yù)備知識(shí)

從定義可以比較容易推出連通雙凱萊圖的以下基本性質(zhì)。

引理1[9]設(shè)H是一個(gè)有限群,R,L,S是H的子集合,滿足1?R∪L,R=R-1,L=L-1,Γ=BiCay(H;R,L,S)是H的一個(gè)雙凱萊圖。如果Γ連通,則以下結(jié)論成立:

(1)H由R∪L∪S生成。

(2) 在同構(gòu)的意義下可以假定S中包含H的單位元。

(3) 對(duì)任意的α∈Aut(H),BiCay(H;R,L,S)?BiCay(Hα;Rα,Lα,Sα)。

(4)BiCay(H;R,L,S)?BiCay(H;L,R,S-1)。

在有限群H中,任取H的兩個(gè)子集U和V,若U與V都非空,則令UV={uv|u∈U,v∈V},否則UV=?。特別地,如果U={u}或V={v},則記UV=uV和UV=Uv。顯然,UV?H。

設(shè)Γ=BiCay(H;R,L,S),|R|=|L|,α是H上一個(gè)既單且滿的映射滿足(1H)α=1H且Rα=L。任取T?V(Γ),則T=M0∪N1,其中M和N是H的子集。令T*=M1∪N0,稱T*是T的共軛集。對(duì)任意的x∈R,令x°αT=(xM)0∪(xαN)1;當(dāng)S=S-1時(shí),令x·T*=(xM)1∪(xN)0,否則令x·T*=(xM)1∪(x-1N)0。如果K?H,令K°αT=∪k∈Kk°αT和K·T*=∪k∈Kk·T*。對(duì)于任意h∈H,NΓ(h0)和NΓ(h1)分別表示h0與h1在Γ中的鄰點(diǎn)集合,則有

NΓ(h0)={(rh)0,(sh)1|r∈R,s∈S},

NΓ(h1)={(rαh)1,(s-1h)0|r∈R,s∈S}。

顯然,∪t∈TNΓ(t)=∪x∈R,y∈S(x°αT∪y·T*)。

由定義可以直接得到命題1和命題2,省略證明。

命題1假定Γ=BiCay(H;R,L,S)是一個(gè)正則的雙凱萊圖,T=M0∪N1?V(Γ),α是H到自身的一個(gè)既單且滿的映射且(1H)α=1,Rα=L。則T是一個(gè)α-擬正規(guī)子集當(dāng)且僅當(dāng)對(duì)任意x∈R,xM=Mx,xαN=Nx,對(duì)任意的y∈S,yM=My,且當(dāng)S≠S-1,y-1N=Ny,當(dāng)S=S-1,yN=Ny

命題2Γ是一個(gè)圖,有下面三個(gè)結(jié)論成立。

(1) 如果T是Γ的完全完備碼,則V(Γ)的|T|個(gè)子集,NΓ(t),t∈T是V(Γ)的一個(gè)劃分。

(2)T0,T1是Γ的兩個(gè)無(wú)公共點(diǎn)的完全完備碼,則|T0|=|T1|,且T0∪T1在Γ中的誘導(dǎo)子圖是一系列無(wú)交偶圈的并。

(3)T是Γ的完全完備碼,對(duì)任意的σ∈Aut(Γ),(T)σ也是Γ的完全完備碼。

2 雙凱萊圖的完全完備碼

定理1揭示了正則雙凱萊圖的完全完備碼與圖的點(diǎn)劃分的密切聯(lián)系。

定理1假定H是有限群,Γ=BiCay(H;R,L,S)是H的一個(gè)正則雙凱萊圖。令T?V(Γ),T=M0∪N1,M與N是H的子集。則對(duì)任意的一個(gè)H到自身的既單且滿的映射α,滿足(1H)α=1H且Rα=L,下述結(jié)論(1)和結(jié)論(2)等價(jià)。此外,若α∈Aut(Γ),S=S-1,那么結(jié)論(3)也與結(jié)論(1)、(2)等價(jià)。

(1)T是Γ的完全完備碼。

(2)T?V(Γ)的|R|+|S|個(gè)子集,x°αT,y·T*是V(Γ)的一個(gè)劃分,其中x∈R,y∈S。

證明注意到(1H)α=1H,1H°αT=T。

(1)?(2):假定T=M0∪N1是Γ的一個(gè)完全完備碼,則T是一個(gè)匹配。根據(jù)命題2,V(Γ)的|M|+|N|個(gè)子集NΓ(m0),NΓ(n1),m∈M,n∈N是

V(Γ)的一個(gè)劃分。因?yàn)镹Γ(m0)={(rm)0,(sm)1|r∈R,s∈S},NΓ(n1)={(rαn)1,(s-1n)0|r∈R,s∈S},這表明V(Γ)的|R|+|S|個(gè)子集,x°αT,y·T*是V(Γ)的一個(gè)劃分,其中x∈R,y∈S。

(2)?(1):假定V(Γ) 的|R|+|S|個(gè)子集,

x°αT,y·T*是V(Γ)的一個(gè)劃分,其中x∈R,y∈S,則V(Γ)=∪t∈TNΓ(t)。而且對(duì)任意的a∈V(Γ),存在唯一的r∈R,唯一的m0,n1∈T,使得a=(rm)0或(rαn)1;或存在唯一的s∈S,唯一的h0,k1∈T*,使得a=(sh)1或(s-1k)0,因此|NΓ(a)∩T|=1。故T是Γ的完全完備碼。

注1 在引理1中雖然可以根據(jù)圖同構(gòu)來(lái)假設(shè)1H∈S,但是該條件的存在與否會(huì)使得V(Γ)的子集有非常大的差異。在定理1的結(jié)論(2)中,若1H∈S,則T*是這些|R|+|S|個(gè)子集中的一個(gè)。反之,T*不一定在這些子集中。

當(dāng)T是一個(gè)完全完備碼時(shí),通過(guò)計(jì)算H0,H1包含在x°αT,y·T*,x∈R,y∈S中的點(diǎn)就可得到T*與H的聯(lián)系。

推論1Γ=BiCay(H;R,L,S)是正則的雙凱萊圖,T=M0∪N1是Γ的一個(gè)完全完備碼,有下述結(jié)論成立:

(1) 當(dāng)M和N都不為空集,且|R|≠|(zhì)S|時(shí),有

證明根據(jù)定理1得,T是Γ的完全完備碼,則V(Γ)的|R|+|S|個(gè)子集,x°αT,y·T*是V(Γ)的一個(gè)劃分,其中x∈R,y∈S,α是H到自身的既單且滿的映射,(1H)α=1H且Rα=L。

注意若T是Γ的完全完備碼時(shí),T的共軛不一定是Γ的完全完備碼。但是,在一定條件下,T和T*可以同時(shí)是完備碼。

引理2Γ=BiCay(H;R,Rα,S)是正則雙凱萊圖,其中α∈Aut(Γ)。令T?V(Γ),T=M0∪N1,M與N是H的子集。如果Mα=M,Nα=N,S=S-1,則T是完全完備碼當(dāng)且僅當(dāng)T*是完全完備碼。特別地,在Haar圖Γ=BiCay(H;?,?,S)中,只要S=S-1,則T是完全完備碼當(dāng)且僅當(dāng)T*是完全完備碼。

證明假定T是完全完備碼。任取h0∈H0,則有(hα)1∈H1。由條件α∈Aut(Γ),Mα=M,Nα=N,S=S-1,則存在唯一的r∈R,n∈N使得(hα)1=(rαnα)1,或唯一的m∈M,s∈S,使得h1=(sm)1。因此h0=(rn)0或(sm)0,r,n,m,s都是唯一確定。考慮到S=S-1,故T*中有且只有一個(gè)點(diǎn)與h0相連。對(duì)于任意的h1∈H1,同理可得T*有且只有一個(gè)點(diǎn)與h1相連。當(dāng)T*是完全完備碼時(shí),同理可證T是完全完備碼。

在Haar圖Γ=BiCay(H;?,?,S)中,假定S=S-1。如果T是Γ的完全完備碼,任取h0∈H0,則h1∈H1而且存在唯一的m∈M,s∈S,使得h1=(sm)1,因此h0=(sm)0,即T*中有且只有一個(gè)點(diǎn)與h0相鄰。對(duì)于任意的h1∈H1,同理可得T*有且只有一個(gè)點(diǎn)與h1相連。因此,T*是完全完備碼。同理可證如果T*是完備碼,那么T也是完全完備碼。

作為一種特殊的情況,下述推論3顯然成立。

在Haar圖Γ=BiCay(H;?,?,S)中,如果T=M0∪N1是完全完備碼,則對(duì)于M0或M1中任意一個(gè)點(diǎn)都有N1或N0中的唯一個(gè)點(diǎn)與之相鄰,反之亦然。再根據(jù)命題1,T是α-擬正規(guī)子集當(dāng)且僅當(dāng)對(duì)任意s∈S,sM=Ms,sN=Ns。令Kn×n表示具有2n個(gè)點(diǎn)的完全二部圖,則有如下結(jié)論。

通過(guò)上述結(jié)論,最終可得到定理4。

定理4Γh=BiCay(H;?,?,S),T=M0∪N1是V(Γ)的一個(gè)子集,S=S-1,對(duì)任意s∈S,有sM=Ms,sN=Ns,則下面條件等價(jià):

(1)T是Γh的完全完備碼。

(2)V(Γh)的2|S|個(gè)子集(sM)1,(sN)0是V(Γh)的一個(gè)劃分,其中s∈S。

(4) 存在覆蓋映射f:?！鶮(S,S)=(U,W),u,w∈V(KS,S)使得f-1(u)=(sM)1且f-1(W)=(sN)0。

3 子群完全完備碼

定理5 假定H是有限群,K是H的子群且K有一個(gè)逆封閉的左橫貫S。則對(duì)任意的L?H,K0是雙凱萊圖Γ=BiCay(H;S,L,S)的一個(gè)完全完備碼。

證明因?yàn)?|S|個(gè)子集(rK)0,(sK)1,r,s∈S是V(Γ)的一個(gè)劃分。根據(jù)定理1,對(duì)任意的L?H,K0是Γ的完全完備碼。

定理6 假定H是有限群,K是H的子群,Γ=BiCay(H;R,Rα,S)是一個(gè)正則雙凱萊圖,其中α是H到自身的一個(gè)既單且滿的映射且滿足(1H)α=1H。對(duì)任意的h∈H,下述結(jié)論成立。

(1)T=K0∪(Kh)1是Γ的完全完備碼,當(dāng)且僅當(dāng)H可以被劃分成|R|+|S|個(gè)子集rK,s-1Kh,r∈R,s∈S,也可以被劃分成|R|+|S|個(gè)子集sK,rαKh,r∈R,s∈S。

(2)T=K0∪K1是Γ的完全完備碼,當(dāng)且僅當(dāng)H可以被劃分成|R|+|S|個(gè)子集rK,s-1K,r∈R,s∈S,也可以被劃分成|R|+|S|個(gè)子集sK,rαK,r∈R,s∈S。

證明根據(jù)定理1,T是Γ的完全完備碼,當(dāng)且僅當(dāng)|R|+|S|個(gè)子集,r°αT,s·T*是V(Γ)的一個(gè)劃分,其中r∈R,s∈S。因?yàn)閞°αT=(rK)0∪(rαKh)1,當(dāng)S=S-1時(shí),有s·T*=(sK)1∪(sKh)0,否則s·T*=(sK)1∪(s-1Kh)0。因此,H0=(rK)0∪(s-1Kh)0和H1=(rαKh)1∪(sK)1,故結(jié)論(1)成立。

因?yàn)镵h=K當(dāng)且僅當(dāng)h∈K,所以結(jié)論(2)是結(jié)論(1)的特殊情況。

證明令α作為H的一個(gè)單位自同構(gòu),根據(jù)命題1,T是一個(gè)α-擬正規(guī)子集。顯然Mα=M,Nα=N。又有S=S-1,根據(jù)推論3可得上述結(jié)論。