由輪生成的Cayley 圖的廣義3 -連通度

張 燕， 馬木提·阿依古麗

（新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊830046）

1 引言及預(yù)備知識

令G ＝（V，E）表示點集為V（G）和邊集為E（G）的圖.任意一點v∈V（G），

NG（v）＝｛u∈V（G）＼｛v｝｜uv∈E（G）｝

表示v在G中的鄰集. v 在G 中的度，記為dG（v），其中dG（v）＝｜NG（v）｜. Δ（G）和δ（G）分別表示G的最大度和最小度.若Δ（G）＝δ（G）＝k，則稱G 是k-正則的.任意點x，y∈V（G），記（x，y）-路P ＝｛x ＝x0，x1，…，xk＝y(tǒng)｝，其起點是x，終點是y，內(nèi)部點是x1，x2，…，xk-1.若路P上的兩點是連續(xù)的，則這兩點是相鄰的.一個長為1 的路是一個邊，簡記xy.若G中的2 條（x，y）-路P 和Q沒有公共內(nèi)部點，則稱它們是內(nèi)部不交的，也就是說，V（P）∩V（Q）＝｛x，y｝.若

則（X，Y）-路是一族由起點為x∈X，終點為y∈Y，且內(nèi)部點既不屬于X，也不屬于Y 的內(nèi)部不交路.特別地，若X ＝｛x｝，則（X，Y）-路是一族由起點為x，終點為Y中不同點的內(nèi)部不交路.對于未提到的圖的理論符號和術(shù)語，參考文獻［1］.

傳統(tǒng)連通度κ（G）是圖G的點子集X的最小基數(shù)，使得G-X 是不連通的或平凡的.若κ（G）≥k，則圖G 是k -連通的.眾所周知，Whitney［2］提出了與連通度等價的定義.若S ＝｛u，v｝是V（G）中的任意一個2 元-子集，則κ（G）表示G 中內(nèi)部不交的（u，v）-路的最大數(shù)目.作為傳統(tǒng)連通度的一個推廣，Chartrand等［3］在1984 年提出了廣義k -連通度.這個參數(shù)可以通過連接圖G中的任意k個點來衡量圖G的容錯性.令G是一個階為n的連通圖，S是圖G中任意一個k 個點的集合，其中k 是整數(shù)，且2≤k≤n，若S?V（T），則稱樹T是G的一個S-樹.令｛T1，T2，…，Tr｝是圖G的S-樹的集合，若

且

其中1≤i≠j≤r，則稱其是內(nèi)部不交的.令κG（S）表示圖G中內(nèi)部不交S-樹的最大數(shù)目，用κk（G）表示圖G的廣義k-連通度，其中

顯然G的廣義2 -連通度κ2（G）恰好是κ（G）.

近幾年，廣義k-連通度受到了一些關(guān)注，Li［4］證明了一般圖G是否存在k個內(nèi)部不交的S-樹是NP-完全問題，其中S?V（G），｜S ｜＝k，且k是固定的整數(shù).目前，已經(jīng)有了關(guān)于廣義連通度的上界和下界的結(jié)果［5］.除此之外，還有一些關(guān)于某類圖的廣義k-連通度的結(jié)果，但大多是關(guān)于k ＝3 或4.例如，Li 等確定了卡氏積圖［6］、星圖［7］、冒泡排序圖［7］及由樹和圈生成的Cayley 圖的廣義3 -連通度［8］.Lin等［9］確定了超立方體的廣義4 -連通度等，其中由圈生成的Cayley 圖—修正冒泡排序圖MBn的廣義3 -連通度的結(jié)果如下：

定理1.1［8］κ3（MBn）＝n-1，其中n≥3.

在本文中，主要研究由輪生成的Cayley 圖WGn，并證明下面的結(jié)論：

定理1.2 κ3（WGn）＝2n-3，其中n≥4.

令Vn是由集合｛1，2，…，n｝生成的n！個不同置換的集合.令p ＝p1p2…pn是Vn中的一個置換，其中pi表示置換p 的第i 位.對換φi，j是一個交換已知置換的第i位和第j位的函數(shù)，其中1≤i ＜j≤n，且一般定義如下：已知p ＝p1p2…pn是Vn中的一個置換，則

Shi［10］提出了有關(guān)Cayley圖Cay（Sym（n），T）的概念，其中Sym（n）是在｛1，2，…，n｝上的對稱群，T是Sym（n）的對換集合. G（T）表示點集是｛1，2，…，n｝，邊集是｛ij ｜（ij）∈T｝的圖，稱G（T）為Cay（Sym（n），T）的生成圖.

若G（T）是一個單圈圖，UGn表示單圈-對換圖Cay（Sym（n），T）.特別地，若G（T）是一個圈，則稱UGn是修正冒泡排序圖MBn.圖1 和圖2 分別表示MB3和MB4.眾所周知，UGn是一個n -正則n-連通二部點傳遞圖.

圖1 由三角形生成的修正冒泡排序圖MB3Fig. 1 The modified bubble sort graph MB3 generated by a triangle

圖2 由C4生成的修正冒泡排序圖MB4Fig. 2 The modified bubble sort graph MB4 generated by C4

若G（T）是一個輪圖Wn，WGn表示輪-對換圖Cay（Sym（n），T），其中輪圖是由一個單點與一個（n-1）-圈上所有點相連形成的圖. W4和WG4如圖3 所示.從定義可知，WGn是一個（2n -2）-正則二部點傳遞圖［11］.

圖3 由輪圖W4生成的Cayley圖WG4Fig. 3 The Cayley graph WG4 generated by wheel graph W4

下面的引理將會用于定理1.2 的證明.

引理1.1［5］若存在2 個度為δ（G）的相鄰點，則κk（G）≤δ（G）-1，其中3≤k≤｜V（G）｜.

引理1.2［1］若G是一個k-連通圖，x是G中的任一點，Y?V＼｛x｝是至少有k個點的集合，則在G中存在k條內(nèi)部不交且終點是Y中不同點的（x，Y）-路.

對每個i∈｛1，2，…，n-3｝，令