兩類圖的Kronecker積的超連通度

馬芳玲,原 軍

(太原科技大學 應用科學學院,太原 030024)

1 介紹

本文用具有頂點集V(G)和邊集E(G)的無向簡單圖G來表示互連網(wǎng)絡。對于簡單圖而言,定義為沒有環(huán),且其中任意兩條連桿沒有同時連接在相同的一對頂點。完全圖定義為任意一對不同的頂點它們之間總會有一條邊連接的簡單圖。從同構的角度分析,由n個頂點組成的完全圖,有且只有一個,記作Kn.完全圖K5如圖1(a)所示。由頂點集X1,X2,…,Xl組成的簡單圖定義為完全l部圖,圖中的所有的頂點,均與在不同子集中的其他頂點相互連接;若|X1|=x1,|X2|=x2,…,|Xl|=xl,則這樣的圖記為T(x1,x2,…,xl).圖1(b)是完全二部圖T(3,3).

圖1 完全圖Fig.1 A complete graph

對于兩個頂點u,v∈V(G), 如果u和v是彼此相鄰的,那么存在一條邊e,使得e=uv.對于任意頂點v,它的度dG(v)是與v本身相關聯(lián)的邊數(shù)。一個圖G,如果對于任何頂點v,都有dG(v)=k,則這個圖為k正則的。對于圖G中任意頂點v,鄰集NG(v)被視作為v的鄰點的集合。如果鄰集和度的記號未出現(xiàn)符號混淆,則可以省略其下標。V中的一個子集S,在G中如果滿足任意兩個頂點都不相鄰,那么稱S是G中的一個獨立集。G中的一個獨立集S被稱為G中的最大獨立集,則滿足不再存在獨立集S′,使得|S′|>|S|成立。這里沒有定義的圖的術語和符號將遵循文獻[1].

設V(G)中任一子集V′,用G-V′來表示,從G中刪去V′的全部頂點所得到的圖。在連通圖G中,使得G-V′不連通的頂點集V′,為圖G的一個頂點割。 其中含k個元素的頂點割,被稱為k頂點割。完全圖是沒有頂點割的;在有一對以上相異的且不相鄰頂點的G中,G的連通度為k頂點割中最小的k,記作к(G);若G的連通度不為最小的k值,則к(G)定義為|V(G)|-1.

連通度是度量互連網(wǎng)絡的可靠性的一個重要參數(shù)指標。通常,互連網(wǎng)絡的可靠性程度可以用它所對應的圖的連通性來衡量。但是,用連通度衡量互連網(wǎng)絡的可靠性某種程度上是存在缺陷的[2],因為連通度假設圖的任何子集中的所有元素都可能同時失效。鑒于此,Harary在文獻[3]中通過提出條件連通度的概念,對這些缺陷進行了彌補。為了讓他們擁有預先得到的性質(zhì),Harary的條件連通度的理念是限制G-V′的分支。基于這一思想,研究人員對經(jīng)典的連通度進行了推廣,提出了超連通度。

超連通度的定義是Francis T.Boesch[4]和A.-H.Esfahanian[5]提出的。如果頂點割S被稱為超頂點割,當且僅當G-S斷開連接且沒有孤立頂點。這個定義意味著對于任意u∈V(G-S),有NG(u)?S.超連通度κ′是所有超頂點割的最小基數(shù),如果有的話,κ′(G)=min{|S|):S?V(G)是G的超頂點割}.Fébrega和Fiol在文獻[6]中對具有大圍長圖的超連通度進行了深入的剖析。圖的超連通度已經(jīng)被一大批學者所研究與探索,參見文獻[7-8].

給定任意兩個圖G1和G2,G1和G2的Kronecker積G1×G2是具有頂點集V(G1×G2)=V(G1)×V(G2)和邊集E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}的圖。圖2為一個圖G和K2的Kronecker積,其中V(G)={u1,u2,u3,u4,u5},V(K2)={v1,v2}.

圖2 Kronecker積(G×K2)Fig.2 The Kronecker product (G×K2)

圖的Kronecker積在圖著色、圖識別和分解、圖嵌入、匹配理論和圖的可靠性等方面有著廣泛的應用[9-10]。因此,圖的Kronecker積得到了很多學者的關注。

在圖的Kronecker積的連通度這一研究領域,Miller[11]和Weichsel[12]對兩個連通圖的Kronecker積的連通度問題開展了研究,對于兩個完全圖,其Kronecker積的連通度被Mamut和Vumar[13]確定,完全圖和二部圖的Kronecker積的連通度已由Guji和Weichsel給出[14]。

這些結果在文獻[15]中得到了推廣。文獻[14]還推導出了任意圖與階大于等于3的完全圖的Kronecker積的連通度公式。有關圖的Kronecker積的更多報告參考文獻[16-19].

2 圖的Kronecker積的超連通度

在本節(jié)討論了完全圖和完全多部圖的Kronecker積的超連通度。

對于劃分為(X1,X2,…,Xl)的多部圖G和完全圖Kn(n≥2), 令V1=V(G)={u1,u2,…,um},V2=V(Kn)={v1,v2,…,vn}.對于1≤i≤m,1≤j≤n,令Sj=V1×{vj},X1j=X1×{vj},X2j=X2×{vj},…,Xij=Xi×{vj},…,Xlj=Xl×{vj}.頂點(ui,vj)簡寫為wij,其中i∈{1,2,…,m},j∈{1,2,…,n}.這意味著對于任意j∈{1,2,…,n},集合Sj=X1j∪X2j∪…∪Xlj={w1j,w2j,…,wij,…,wmj}是G×Kn中的一個獨立集,且V(G×Kn)有一個劃分V(G×Kn)=S1∪S2∪S3∪…∪Sn.

定理1[12]設G1和G2為連通圖。圖H=G1×G2是連通的當且僅當G1或G2包含一個奇圈。

引理1[12]設G連通圖。如果G沒有奇圈,那么G×K2恰好有兩個同構于G的連通分支。

完全l部圖是頂點集劃分為X1,X2,…,Xl的一個簡單圖,設T(x1,x2,…,xl)是滿足|Xi|=xi的完全多部圖,Kn為V(Kn)={v1,v2,…,vn}的完全圖。

引理3設S是V(T(x1,x2,…,xl)×Kn)的子集,至少三個不同的i值,i∈{1,2,…,n},使得SiS≠?.如果(T(x1,x2,…,xl)×Kn)-S沒有孤立的頂點,則它是連通的。

證明假設存在滿足給定條件的S,至少三個不同的i值,i∈{1,2,…,n},使得SiS≠?.(T(x1,x2,…,xl)×Kn)-S不存在孤立頂點,且是不連通的。

不妨設i∈{1,2,3},S1S≠?,S2S≠?,S3S≠?和一些ji∈{1,2,…,m},存在頂點wjii∈SiS.為了便于表示,將wjii縮寫為wi,并考慮關于這三個頂點的以下三種情形。

情形1頂點集{w1,w2,w3}在某Xi×V(Kn)中。

不妨設{w1,w2,w3}?X1×V(Kn).由于(T(x1,x2,…,xl)×Kn)-S是不連通的,將進一步劃分為兩種子情形。

情形1.1 三個頂點{w1,w2,w3}并不都在同一個分支中。這意味著這些頂點中至少有一個頂點與其它兩個頂點在不同的分支中。設C是(T(x1,x2,…,xl)×Kn)-S的一個分支且w3∈C,w1?C,w2?C.頂點割S必須包含不同分支中頂點的公共鄰點。由Kronecker積定義得:

w1∈X1×{v1}=X11,

w2∈X1×{v2}=X12,

w3∈X1×{v3}=X13,

因此,

NT(x1,x2,…,xl)×Kn(w1)∩NT(x1,x2,…,xl)×Kn(w3)=

NT(x1,x2,…,xl)×Kn(w2)∩NT(x1,x2,…,xl)×Kn(w3)=

即:

在這種情況下,NT(x1,x2,…,xl)×Kn(w3)?S.因此(T(x1,x2,…,xl)×Kn)-S包含一個孤立頂點w3.這與假設的(T(x1,x2,…,xl)×Kn)-S不存在孤立頂點相矛盾。

情形1.2 三個頂點{w1,w2,w3}在同一分支中,記為C.因為(T(x1,x2,…,xl)×Kn)-S不連通,存在一個頂點w∈(T(x1,x2,…,xl)×Kn)-S,使得w∈V(C′),其中C′≠C.現(xiàn)在,

NT(x1,x2,…,xl)×Kn(w1)∪NT(x1,x2,…,xl)×Kn(w2)∪

因此,w∈X1×V(Kn).w代替w3,變回情形1.1,由情形 1.1推出矛盾。

情形2{w1,w2,w3}中存在兩個頂點在某Xi×V(Kn)中,另一個頂點在Xj×V(Kn)中,其中j≠i.不妨設{w1,w2}?X1×V(Kn),以及w3∈X2×V(Kn).在這種情況下,因為:

w1=wji1∈X1×{v1}=X11,

w2=wji2∈X1×{v2}=X12,

w3=wji3∈X2×{v3}=X23,

假設:

w1=wj11=(uj1,v1),

w2=wj22=(uj2,v2),

w3=wj33=(uj3,v3),

其中uj1,uj2∈X1,uj3∈X2.所以{w1,w2}?NT(x1,x2,…,xl)×Kn(w3),顯然它們在同一分支中,記為C.因為(T(x1,x2,…,xl)×Kn)-S不連通,故存在一個頂點w∈(T(x1,x2,…,xl)×Kn)-S,使得w∈V(C′),其中C′≠C.現(xiàn)在,因為

所以:

w?NT(x1,x2,…,xl)×Kn(w1)∪NT(x1,x2,…,xl)×Kn(w2)∪

這樣w∈X13?X1×V(Kn).w代替w3,變回情形1.1,由情形1.1推出矛盾。

情形3{w1,w2,w3}中的每個頂點都在不同的Xi×V(Kn).假設{w1}?X1×V(Kn),

{w2}?X2×V(Kn),{w3}?X3×V(Kn).在這種情況下,因為:

w1=wji1=(uji,v1)∈X1×{v1}=X11,

w2=wji2=(uji,v2)∈X2×{v2}=X22,

w3=wji3=(uji,v3)∈X3×{v3}=X33,

3 結束語