李建勛,王 燕

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

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

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

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

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

定義2設(shè)H是一個有限群,R,L,S是H的子集合,滿足1?R∪L,R=R-1,L=L-1。定義H關(guān)于R,L,S的雙凱萊圖,記作Γ=BiCay(H;R,L,S)。其中Γ的點集合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=?,則稱Γ是一個Haar圖,關(guān)于Haar圖,可以參考文獻(xiàn)[7]。

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

1 預(yù)備知識

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

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

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

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

(3) 對任意的α∈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的兩個子集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上一個既單且滿的映射滿足(1H)α=1H且Rα=L。任取T?V(Γ),則T=M0∪N1,其中M和N是H的子集。令T*=M1∪N0,稱T*是T的共軛集。對任意的x∈R,令x°αT=(xM)0∪(xαN)1;當(dāng)S=S-1時,令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*。對于任意h∈H,NΓ(h0)和NΓ(h1)分別表示h0與h1在Γ中的鄰點集合,則有

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)是一個正則的雙凱萊圖,T=M0∪N1?V(Γ),α是H到自身的一個既單且滿的映射且(1H)α=1,Rα=L。則T是一個α-擬正規(guī)子集當(dāng)且僅當(dāng)對任意x∈R,xM=Mx,xαN=Nx,對任意的y∈S,yM=My,且當(dāng)S≠S-1,y-1N=Ny,當(dāng)S=S-1,yN=Ny

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

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

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

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

2 雙凱萊圖的完全完備碼

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

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

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

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

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

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

V(Γ)的一個劃分。因為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|個子集,x°αT,y·T*是V(Γ)的一個劃分,其中x∈R,y∈S。

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

x°αT,y·T*是V(Γ)的一個劃分,其中x∈R,y∈S,則V(Γ)=∪t∈TNΓ(t)。而且對任意的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)來假設(shè)1H∈S,但是該條件的存在與否會使得V(Γ)的子集有非常大的差異。在定理1的結(jié)論(2)中,若1H∈S,則T*是這些|R|+|S|個子集中的一個。反之,T*不一定在這些子集中。

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

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

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

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

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

引理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*中有且只有一個點與h0相連。對于任意的h1∈H1,同理可得T*有且只有一個點與h1相連。當(dāng)T*是完全完備碼時,同理可證T是完全完備碼。

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

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

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

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

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

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

(2)V(Γh)的2|S|個子集(sM)1,(sN)0是V(Γh)的一個劃分,其中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有一個逆封閉的左橫貫S。則對任意的L?H,K0是雙凱萊圖Γ=BiCay(H;S,L,S)的一個完全完備碼。

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

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

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

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

證明根據(jù)定理1,T是Γ的完全完備碼,當(dāng)且僅當(dāng)|R|+|S|個子集,r°αT,s·T*是V(Γ)的一個劃分,其中r∈R,s∈S。因為r°αT=(rK)0∪(rαKh)1,當(dāng)S=S-1時,有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)成立。

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

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