由2-樹生成的Cayley圖的容錯(cuò)極大局部連通性

羅祖文,徐麗瓊

(集美大學(xué)理學(xué)院，福建 廈門 361021)

0 引言

互連網(wǎng)絡(luò)通常以圖為模型,其中圖的頂點(diǎn)和邊分別對(duì)應(yīng)互連網(wǎng)絡(luò)的處理器和通信線路。設(shè)G=(V(G),E(G))是一個(gè)無向圖,其中V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集。對(duì)于圖G中任意一頂點(diǎn)u,用NG(u)表示G中與u相鄰的頂點(diǎn)的集合。頂點(diǎn)u的度dG(u)表示在G中與u相鄰的頂點(diǎn)的數(shù)目,度為0的頂點(diǎn)稱為孤立點(diǎn),δ(G)表示圖G的最小度。設(shè)x,y是圖G中兩個(gè)不相鄰的頂點(diǎn),則x-y-點(diǎn)割是指V(G){x,y}的一個(gè)頂點(diǎn)子集S,使得x和y屬于G-S的不同連通分支。圖G的連通度κ(G)是指最小的頂點(diǎn)數(shù)k使得刪除這些頂點(diǎn)后圖G不連通或者只有一個(gè)頂點(diǎn)。若κ(G)≥k,則稱G是k連通。若κ(G)=δ(G),則稱G為極大連通圖。k-樹圖是k連通圖的一種,其有著諸多有趣的組合性質(zhì)。很多NP-困難問題在有限的k-樹圖中都有多項(xiàng)式算法。n階k-樹圖Tk,n的遞歸定義[1]為:k個(gè)兩兩相鄰的頂點(diǎn)構(gòu)成k-樹圖Tk,k,在k-樹圖Tk,n-1上任取k個(gè)兩兩相鄰的頂點(diǎn),添加一個(gè)新的頂點(diǎn)與這k個(gè)兩兩相鄰的頂點(diǎn)都相鄰得到一個(gè)k-樹圖Tk,n。k-樹圖是樹的推廣,k=1時(shí),即為樹。本文未予定義而直接使用的符號(hào)和術(shù)語(yǔ)見文獻(xiàn)[2]。

關(guān)于容錯(cuò)極大局部連通和容錯(cuò)一對(duì)多極大局部連通,許多互連網(wǎng)絡(luò)已被研究,包括超立方體[3]、折疊超立方體[4]、星圖[5]、冒泡排序圖[6]、由對(duì)換樹生成的Cayley圖[7]、冒泡排序星圖[8]和交錯(cuò)群圖[9]等。

通常衡量一個(gè)互連網(wǎng)絡(luò)好壞的標(biāo)準(zhǔn)是:對(duì)稱性,可擴(kuò)展性,短直徑,簡(jiǎn)單方便的最優(yōu)路由,遞歸結(jié)構(gòu),平行路的存在性等。Cayley網(wǎng)絡(luò)作為一種正則、點(diǎn)對(duì)稱的互連網(wǎng)絡(luò)倍受人們的青睬,它在計(jì)算機(jī)互連網(wǎng)絡(luò)的設(shè)計(jì)與分析中起著重要的作用?；诖?本文主要研究由2-樹生成的Cayley圖的容錯(cuò)極大局部連通性和容錯(cuò)一對(duì)多極大局部連通性。

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

在設(shè)計(jì)和選擇互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí),要考慮的一個(gè)重要問題是它的可靠性,而圖的連通度是衡量網(wǎng)絡(luò)可靠性的最重要參數(shù)之一。對(duì)于圖的連通度,Menger[10]從局部的角度出發(fā),定義任意兩個(gè)頂點(diǎn)的局部連通度κ(u,v)為這兩個(gè)頂點(diǎn)之間內(nèi)部頂點(diǎn)不交路的數(shù)目的最大值,并給出關(guān)于局部連通度的一個(gè)經(jīng)典的結(jié)果,即Menger定理。

定理1[10]設(shè)x和y是圖G中兩個(gè)不相鄰的頂點(diǎn),則x和y的局部連通度等于x-y-頂點(diǎn)割所含的最小頂點(diǎn)數(shù)。

結(jié)合極大連通圖和局部連通度的定義,Oh等[5，11]給出了關(guān)于極大局部連通和f-容錯(cuò)極大局部連通的概念。

定義1[11]若對(duì)于圖G中任意兩個(gè)頂點(diǎn)u和v，都有κ(u,v)=min{d(u),d(v)},則稱圖G是極大局部連通的。

定義2[5]設(shè)f是正整數(shù),對(duì)于圖G的任意階不超過f的頂點(diǎn)子集F,有G-F是極大局部連通的,則稱G是f容錯(cuò)極大局部連通的。

上述定義可推廣至一個(gè)頂點(diǎn)對(duì)多個(gè)頂點(diǎn)的情況。

在G中,給定一個(gè)頂點(diǎn)x和一個(gè)頂點(diǎn)子集Y，滿足|Y|≥k,稱x到Y(jié)之間的k條終點(diǎn)兩兩不同的內(nèi)部頂點(diǎn)不交路為x到Y(jié)的一個(gè)k扇。設(shè)F?V(G),G-F中存在頂點(diǎn)集Y，滿足|Y|≤dG-F(x),并且對(duì)任一頂點(diǎn)v∈Y,有{v}∪NG-F(v)Y,則稱Y為關(guān)于x和F的條件終點(diǎn)集,簡(jiǎn)稱條件終點(diǎn)集。文獻(xiàn)[2]推廣Menger定理,得到如下結(jié)果。

定理2[2]設(shè)G是k連通的,x∈V(G),Y?V(G){x}滿足|Y|≥k,則在G中存在x到Y(jié)的一個(gè)k扇。

結(jié)合上述定理,Shih等[6]給出一對(duì)多形式的容錯(cuò)極大局部連通的定義。

定義3[6]設(shè)F是G的頂點(diǎn)子集滿足|F|≤f,x∈V(G-F),Y是G-F中關(guān)于x的任意條件終點(diǎn)集,若在G-F中x和Y之間存在|Y|條終點(diǎn)兩兩不同的內(nèi)部頂點(diǎn)不交路,則稱G為一對(duì)多f容錯(cuò)極大局部連通的。

設(shè)Γ是一個(gè)有限群,Δ是Γ不含單位元的子集,定義一個(gè)有向圖G如下：它的頂點(diǎn)集是Γ,弧集是{(g,gs):g∈Γ,s∈Δ}。

如此定義的有向圖G稱為群Γ關(guān)于子集Δ的Cayley圖,記為Γ(Δ)。若對(duì)任意的s∈Δ,有s-1∈Δ,則此時(shí)Cayley圖為無向Cayley圖。當(dāng)Γ是交錯(cuò)群An,Δ={(1,2,3),(2,1,3),(1,2,4),(2,1,4),…,(1,2,n),(2,1,n)}時(shí),稱Γ(Δ)為交錯(cuò)群圖,記為AGn。方便起見,用階為n的圖來描述AGn的生成集,生成集里的每一個(gè)元素(abc)及它的逆(bac)用一個(gè)三角形K3表示,如圖1所示。這種通過K3來表示生成集的元素的圖稱為AGn的3循環(huán)生成圖,或簡(jiǎn)稱為AGn的生成圖。AGn的生成圖是一棵特殊的2-樹。

當(dāng)Γ是交錯(cuò)群An,生成圖是一般的2-樹時(shí),稱Γ(Δ)為由2-樹T2,n生成的Cayley圖,記為An(Δ)[12]。由2-樹生成的Cayley圖是交錯(cuò)群圖的推廣。由2-樹生成的Cayley圖的生成集Δ里有2n-4個(gè)3循環(huán),所以Γn(Δ)是一個(gè)階為n!/2的(2n-4)正則圖。當(dāng)n=4時(shí),A4(Δ)為交錯(cuò)群圖AG4,如圖2所示。

在證明本文的主要結(jié)果之前,首先引用一些已證明的結(jié)論。

引理1[13]當(dāng)n≥4時(shí),由2-樹T2,n生成的Cayley圖An(Δ)是(2n-4)連通的。

引理2[13]設(shè)T是An(Δ)的頂點(diǎn)子集滿足|T|≤4n-12。當(dāng)n≥5時(shí),An(Δ)-T滿足下述條件之一：1)An(Δ)-T是連通的；2)An(Δ)-T有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)。

引理3[13]設(shè)T是An(Δ)的頂點(diǎn)子集滿足|T|≤6n-20。當(dāng)n≥5時(shí),An(Δ)-T滿足下述條件之一：1)An(Δ)-T是連通的；2)An(Δ)-T有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)或者K2;3)An(Δ)-T有3個(gè)分支,其中2個(gè)分支是孤立點(diǎn)。

引理4[12]當(dāng)n≥4時(shí),An(Δ)不包含K4-e和K2,3作為其子圖。

2 主要結(jié)果及其證明

由引理1知，n≥4時(shí),An(Δ)是極大連通圖,結(jié)合定理1可知，An(Δ)中任意一對(duì)頂點(diǎn)都被2n-4條內(nèi)部頂點(diǎn)不交路連接。由于網(wǎng)絡(luò)中故障的發(fā)生是不可避免的,下面對(duì)An(Δ)的極大局部連通性進(jìn)行容錯(cuò)性分析。

引理5 設(shè)F是G=An(Δ)的頂點(diǎn)子集滿足|F|≤4n-13,e是G的一條邊,當(dāng)n≥5時(shí),G-F-{e}滿足下列條件之一：1)G-F-{e}是連通的；2)G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)。

證明在G中任取一條邊e=xy,由引理2,可得x,y?F,否則引理成立。假設(shè)G-F-{e}不連通,令F′=F∪{x},則|F′|≤4n-12。由引理2,若G-F′連通,則G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)x,滿足條件2);若G-F′不連通,由引理2,G-F′有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)，設(shè)為u,另一個(gè)大分支設(shè)為C,此時(shí)NG(u)?F′。下面分2種情況考慮。

情況1ux∈E(G)。

由引理4,|NG(x)∩NG(u)|≤1,從而dF(x)≤|F|-dG(u)+1+1≤2n-7,因此dC(x)≥2n-4-1-(2n-7)=2。又G-F-{e}不連通,顯然y?C。此時(shí)u=y,G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,滿足條件2)。

情況2ux?E(G)。

由引理4,|NG(x)∩NG(u)|≤2,從而dF(x)≤|F|-dG(u)+2≤2n-7,因此dC(x)≥2n-4-(2n-7)=3,顯然y∈C,此時(shí)G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,滿足條件2)。

定理3 設(shè)F是G=An(Δ)的頂點(diǎn)子集滿足|F|≤2n-7,當(dāng)n≥5時(shí),G-F中任意一對(duì)頂點(diǎn)u和v都被min{dG-F(u),dG-F(v)}條內(nèi)部頂點(diǎn)不交路連接,即G是(2n-7)容錯(cuò)極大局部連通的。

證明當(dāng)n≥5時(shí),設(shè)u和v是G-F中任意2個(gè)不同的頂點(diǎn),令m=min{dG-F(u),dG-F(v)},則m≤2n-4。下面分2種情況用反證法證明。

情況1uv?E(G)。

假設(shè)在G-F中u和v之間不存在m條內(nèi)部頂點(diǎn)不交路,由定理1可知,在G-F中存在一頂點(diǎn)子集T滿足|T|≤m-1,使得刪去這個(gè)頂點(diǎn)集后,得到的子圖G-F-T中u和v不連通。又|F|+|T|≤2n-7+m-1≤4n-12,由引理2知G-F-T或者連通,或者有2個(gè)分支,其中一個(gè)是孤立點(diǎn)。當(dāng)G-F-T連通時(shí),與u和v在G-F-T中不連通矛盾。當(dāng)G-F-T不連通時(shí),則G-F-T有2個(gè)分支,其中一個(gè)是孤立點(diǎn),設(shè)為x,又在G-F-T中u和v不連通,則u=x或v=x。不失一般性，設(shè)u=x,則NG-F(u)?T,從而|T|≥dG-F(u)≥m,這與|T|≤m-1矛盾。

情況2uv∈E(G)。

假設(shè)在G-F-uv中u和v之間不存在m-1條內(nèi)部頂點(diǎn)不交路,由定理1可知,在G-F-uv中存在一個(gè)頂點(diǎn)集T滿足|T|≤m-2,使得刪去這個(gè)頂點(diǎn)集后,得到的子圖G-F-T-uv中u和v不連通。又|F|+|T|≤2n-7+m-2≤4n-13,由引理5知,G-F-T-uv或者是連通的,或者有2個(gè)分支,其中一個(gè)是孤立點(diǎn)。當(dāng)G-F-T-uv連通時(shí),與u和v在G-F-T-uv中不連通矛盾。當(dāng)G-F-T-uv不連通時(shí),它有2個(gè)分支,其中一個(gè)是孤立點(diǎn),設(shè)為y,又因?yàn)閡和v在G-F-T-uv中不連通,則u=y或v=y。不失一般性，設(shè)u=y,則NG-F-uv(u)?T,從而|T|≥dG-F-uv(u)≥m-1,這與|T|≤m-2矛盾,定理得證。

當(dāng)n≥5時(shí),給出一個(gè)例子說明定理3中的容錯(cuò)極大局部連通性的結(jié)果是緊的。由2-樹生成的Cayley圖G的構(gòu)造可知G包含K3作為其子圖,如圖3所示,設(shè)u,v,w是G中兩兩相鄰的3個(gè)頂點(diǎn),由引理4可知u,v只有一個(gè)公共鄰點(diǎn)w。令F=NG(u){w,v},x∈V(G)-(NG(u)∪NG(v)),則|F|=2n-6,m=min{dG-F(x),dG-F(v)}=2n-4。此時(shí)令T=NG(v){u},顯然T?G-F滿足|T|=2n-5=m-1,且在G-F-T中x和v不連通。由定理1,在G-F中x和v之間不存在min{dG-F(x),dG-F(v)}=2n-4條內(nèi)部頂點(diǎn)不交路。

定理4 設(shè)F是G=An(Δ)的頂點(diǎn)子集滿足|F|≤2n-7,x∈V(G-F),Y是G-F-{x}中關(guān)于x的任一條件終點(diǎn)集,滿足|Y|=t≤dG-F(x)≤2n-4。當(dāng)n≥5時(shí),G-F中x和Y之間存在t條終點(diǎn)兩兩不同的內(nèi)部頂點(diǎn)不交路,即G是一對(duì)多(2n-7)容錯(cuò)極大局部連通的。

證明當(dāng)n≥5時(shí),由定理2,只需證明對(duì)于任意的T?V(G-F)滿足|T|≤t-1,在G-F-T中x與Y-T之間有一條路即可。用反證法證明,假設(shè)在G-F-T中x與Y-T不連通,則G-F-T不連通,又|F|+|T|≤4n-12,由引理2，G-F-T包含一個(gè)大分支C和一個(gè)孤立點(diǎn)u。所以NG-F(u)?T,如果x=u,則|T|≥dG-F(x)≥t,與|T|≤t-1矛盾。如果x∈C,則u∈Y-T。如果|Y∩T|=t-1,有T?Y,則{u}∪NG-F(u)?Y,與Y是一個(gè)條件終點(diǎn)集矛盾。所以|Y∩T|≤t-2,則(Y-T)∩C≠?。令u′∈(Y-T)∩C,然而在G-F-T中x與u′之間存在一條路,與在G-F-T中x與Y-T不連通矛盾。證畢。

當(dāng)n≥5時(shí),給出一個(gè)例子說明定理4中的一對(duì)多容錯(cuò)極大局部連通性的結(jié)果是緊的。如圖3所示,設(shè)u,v,w是由2-樹生成的Cayley圖G中兩兩相鄰的3個(gè)頂點(diǎn),由引理4可知，u,v只有一個(gè)公共鄰點(diǎn)w。令F′=NG(u) {w,v},Y={v}∪(NG(v){w}),x∈V(G)-(NG(u)∪NG(v)),則|F′|=2n-6,Y?G-F′滿足|Y|=t=dG-F′(x)=2n-4。顯然Y是關(guān)于x和F′的條件終點(diǎn)集,此時(shí)令T′=(Y{u,v})∪{w},則|T′|=t-1且在G-F′-T′中x與{u,v}不連通。由定理2,在G-F′中x和Y之間不存在t=2n-4條終點(diǎn)兩兩不同的內(nèi)部頂點(diǎn)不交路。

由定理3可知,An(Δ)是(2n-7)容錯(cuò)極大局部連通的,但是若在同一頂點(diǎn)處存在2n-6個(gè)故障點(diǎn),結(jié)果并不能被保證。在大多數(shù)情況下,所有故障都發(fā)生在一個(gè)頂點(diǎn)身上概率很小,所以限制每個(gè)頂點(diǎn)有至少3個(gè)無故障相鄰頂點(diǎn)。在此條件限制下,證明了由2-樹生成的Cayley圖An(Δ)是(4n-15)容錯(cuò)極大局部連通的。

引理6 設(shè)F是G=An(Δ)的頂點(diǎn)子集滿足|F|≤6n-21,e是G的一條邊,當(dāng)n≥5時(shí),G-F-{e}滿足下列條件之一：1)G-F-{e}是連通的；2)G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)或者K2;3)G-F-{e}有3個(gè)分支,其中2個(gè)分支是孤立點(diǎn)。

證明在G中任取一條邊e=xy,由引理3,可得x,y?F,否則定理成立。假設(shè)G-F-{e}不連通,令F′=F∪{x},|F′|≤6n-20。若G-F′連通,則G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)x,滿足條件2)。若G-F′不連通,由引理3,下面分3種情況考慮。

情況1G-F′有2個(gè)分支,其中一個(gè)是孤立點(diǎn)u,另一個(gè)是大分支C。

若ux∈E(G)。由于dG(x)=2n-4,此時(shí)對(duì)dC(x)進(jìn)行討論。若dC(x)=0,此時(shí)u=y,則G-F-{e}有3個(gè)分支,其中2個(gè)分支分別是孤立點(diǎn)x和孤立點(diǎn)u,滿足條件3)。若dC(x)=1,當(dāng)u=y時(shí),G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,滿足條件2),當(dāng)u≠y時(shí),則y∈C,此時(shí)G-F-{e}有2個(gè)分支,其中一個(gè)分支是K2,滿足條件2)。若dC(x)≥2,由于G-F-{e}不連通,則u=y,此時(shí)G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,滿足條件2)。

若ux?E(G)。由于ux?E(G),則y∈C,此時(shí)dC(x)≥1。若dC(x)=1,則G-F-{e}有3個(gè)分支,其中2個(gè)分支分別是孤立點(diǎn)x和孤立點(diǎn)u,滿足條件3)。若dC(x)≥2,則G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,滿足條件2)。

情況2G-F′有2個(gè)分支,其中一個(gè)是K2,記為uv,另一個(gè)大分支是C。

若ux∈E(G),vx?E(G)或vx∈E(G),ux?E(G)。不失一般性,設(shè)ux∈E(G),vx?E(G)。由引理4,|NG(u)∪NG(v)|≥4n-11,則dF(x)≤|F|-(4n-11-1)+1+1≤2n-7,因此dC(x)≥2n-4-(2n-7)-1=2。由于G-F-{e}不連通,則y=u,此時(shí)G-F-{e}有2個(gè)分支,其中一個(gè)分支是K2,即uv。滿足條件2)。

若ux∈E(G)且vx∈E(G)。由引理4,dF(x)≤|F|-(4n-11-1)≤2n-9,因此dC(x)≥2n-4-2-(2n-9)=3。此時(shí)G-F-{e}連通,與假設(shè)矛盾。

若ux?E(G)且vx?E(G)。由引理4,dF(x)≤|F|-(4n-11)+2×2≤2n-6,因此dC(x)≥2n-4-(2n-6)=2。此時(shí)G-F-{e}有2個(gè)分支,其中一個(gè)分支是K2,即uv,滿足條件2)。

情況3G-F′有3個(gè)分支,其中2個(gè)是孤立點(diǎn)u和孤立點(diǎn)v,另一個(gè)大分支是C。

若ux∈E(G),vx?E(G)或vx∈E(G),ux?E(G)。不失一般性,設(shè)ux∈E(G),vx?E(G)。由引理4,|NG(u)∪NG(v)|≥4n-10,則dF(x)≤|F|-(4n-10-1)+1+2≤2n-7,因此dC(x)≥2n-4-(2n-7)-1=2。若y∈C,則G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)v,滿足條件2)。若y=u,則G-F-{e}有3個(gè)分支,其中2個(gè)是孤立點(diǎn)u和v,滿足條件3)。

若ux∈E(G)且vx∈E(G)。由引理4,dF(x)≤|F|-(4n-10-1)+1+1≤2n-8,因此dC(x)≥2n-4-(2n-8)-2=2。由于G-F-{e}不連通,則y∈{u,v},不失一般性,令y=u,此時(shí)G-F-{e}有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,滿足條件2)。

若ux?E(G)且vx?E(G)。由引理4,dF(x)≤|F|-(4n-10)+2×2≤2n-7,因此dC(x)≥2n-4-(2n-7)=3。顯然y∈C,則G-F-{e}有3個(gè)分支,其中2個(gè)分支是孤立點(diǎn)u和v,滿足條件3)。

定理5 設(shè)F是G=An(Δ)的頂點(diǎn)子集滿足δ(G-F)≥3且|F|≤4n-15,當(dāng)n≥5時(shí),G-F中任意一對(duì)頂點(diǎn)x和y都被min{dG-F(x),dG-F(y)}條內(nèi)部頂點(diǎn)不交路連接。

證明當(dāng)n≥5時(shí),設(shè)x和y是G-F中任意2個(gè)不同的頂點(diǎn),令m=min{dG-F(x),dG-F(y)},則3≤m≤2n-4。下面分2種情況用反證法證明。

情況1xy?E(G)。

假設(shè)在G-F中x和y之間不存在m條內(nèi)部頂點(diǎn)不交路,由定理1可知,在G-F中存在一頂點(diǎn)子集T滿足|T|≤m-1,使得刪去這個(gè)頂點(diǎn)集后,得到的子圖G-F-T中x和y不連通。又|F|+|T|≤4n-15+m-1≤6n-20,由引理3：

1)若G-F-T有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,另一個(gè)大分支是C。由于G-F-T中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T,因此|T|≥dG-F(x)≥m,與|T|≤m-1矛盾。

2)若G-F-T有2個(gè)分支,其中一個(gè)分支是K2,記為uv,另一個(gè)大分支是C。由于G-F-T中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T∪{v},于是m-1≥|T|≥dG-F(x)-1≥m-1,因此|T|=m-1,NG-F(x)=T∪{v},又由引理4,|NG(x)∩NG(v)|≤1,則dG-F(v)≤2,與δ(G-F)≥3矛盾。

3)若G-F-T有3個(gè)分支,其中2個(gè)是孤立點(diǎn)u和v,另一個(gè)大分支是C。由于G-F-T中x和y不連通,若{x,y}={u,v},不失一般性,令x=u,y=v,顯然NG-F(x)∪NG-F(y)?T,由引理4,2m-2≤dG-F(x)+dG-F(y)-2≤|T|≤m-1,與m≥3矛盾。若x∈{u,v},y∈C,不失一般性,令x=u,y∈C,顯然NG-F(x)∪NG-F(v)?T,又dG-F(v)≥3,由引理4,m+3-2≤dG-F(x)+dG-F(v)-2≤|T|≤m-1,矛盾。

情況2xy∈E(G)。

假設(shè)在G-F-xy中x和y之間不存在m-1條內(nèi)部頂點(diǎn)不交路,由定理1可知,在G-F-xy中存在一頂點(diǎn)子集T滿足|T|≤m-2,使得刪去這個(gè)頂點(diǎn)集后,得到的子圖G-F-T-xy中x和y不連通。又|F|+|T|≤4n-15+m-2≤6n-21，由引理6：

1)若G-F-T-xy有2個(gè)分支,其中一個(gè)分支是孤立點(diǎn)u,另一個(gè)大分支是C。由于G-F-T-xy中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T∪{y},因此|T|≥dG-F(x)-1≥m-1,與|T|≤m-2矛盾。

2)若G-F-T-xy有2個(gè)分支,其中一個(gè)分支是K2,記為uv,另一個(gè)大分支是C。由于G-F-T-xy中x和y不連通,不失一般性,令x=u,y∈C,顯然NG(x)?F∪T∪{v,y},于是m-2≥|T|≥dG-F(x)-2≥m-2,因此|T|=m-2,NG-F(x)=T∪{v,y},又由引理4,|NG(x)∩NG(v)|≤1,則dG-F(v)≤2,與δ(G-F)≥3矛盾。

3)若G-F-T-xy有3個(gè)分支,其中2個(gè)是孤立點(diǎn)u和v,另一個(gè)大分支是C。由于G-F-T-xy中x和y不連通,若{x,y}={u,v},不失一般性,令x=u,y=v,顯然NG-F(x)∪NG-F(y)?T∪{x,y},由引理4,2m-1≤dG-F(x)+dG-F(y)-1≤|T|+2≤m,與m≥3矛盾。若x∈{u,v},y∈C,不失一般性,令x=u,y∈C,顯然NG-F(x)∪NG-F(v)?T∪{y},又dG-F(v)≥3,由引理4,m+3-2≤dG-F(x)+dG-F(v)-2≤|T|+1≤m-1,矛盾。

3 結(jié)論

本文研究了由2-樹生成的Cayley圖的極大局部連通容錯(cuò)性,當(dāng)刪除不超過2n-7個(gè)頂點(diǎn)時(shí),導(dǎo)出子圖中任意一對(duì)頂點(diǎn)x和y都被min{d′(x),d′(y)}條內(nèi)部頂點(diǎn)不交路連接,d′(x),d′(y)分別表示頂點(diǎn)x和y在頂點(diǎn)刪除圖中的度。同時(shí),也證明了由2-樹生成的Cayley圖是一對(duì)多(2n-7)極大局部連通。進(jìn)一步,如果每個(gè)頂點(diǎn)都被限制至少有3個(gè)無故障鄰點(diǎn),由2-樹生成的Cayley圖是(4n-15)極大局部連通,網(wǎng)絡(luò)容錯(cuò)性相應(yīng)增加。本文主要研究的是網(wǎng)絡(luò)中處理器發(fā)生問題(去點(diǎn))的情況,如果通訊線路發(fā)生問題(去邊)，是否也能有相應(yīng)的結(jié)果呢?這將是一個(gè)值得研究的問題。